f033 - 攗皥蒽快給我去工作！！！- 續
題目描述
題目描述了攗皥蒽不斷被欺負和搶錢的故事，並給出一個工作賺錢的場景。總共有 n 天的工作，每天的工資 a_i。需要處理 q 個查詢，查詢分為兩種：
- 更新：將第 p 天的工資修改為 c。
- 查詢：找到最小的 x，使得從第 1 天到第 x 天的工資總和大於等於 k。如果無法達到，輸出 "meh"。
解題思路
這題可以使用分塊 (Block Decomposition) 來優化查詢和更新操作。
- 分塊： 將 n 個工作分成若干塊，每塊包含 len = sqrt(n) 個工作。
- 預處理： 計算每個塊的總和 (global)，並儲存每個塊中的所有工資 (local)。
- 更新： 當需要更新工資時，找到對應的塊，更新該塊的總和和該塊中的工資。
- 查詢： 當需要查詢時，從第一塊開始累加塊的總和，直到總和大於等於 k。然後，在最後一個塊中，逐個累加工資，直到總和大於等於 k。
使用分塊可以將更新和查詢的平均時間複雜度降低到 sqrt(n)。
複雜度分析
- 時間複雜度: O(n + q * sqrt(n))
- 預處理 (build): O(n)
- 更新 (update): O(sqrt(n))
- 查詢 (query): O(sqrt(n))
- 總體: O(n + q * sqrt(n))
- 空間複雜度: O(n)
- 儲存每個塊的工資和總和需要 O(n) 空間。
程式碼
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
//分塊結構
//假設要求區間總和
struct blk{
vector<long long> local; //每塊的全部元素
long long global; //儲存每塊的總和
blk(){ //初始化
local.clear(); //清空區間元素
global = 0; //將區間總和先設為0
}
};
long long n,m,x,z,len,num;
vector<blk> b(500005);
void build(){
len=sqrt(n);
//cout << "len = " << len << "\n";
num=(n+len-1)/len;
long long input;
for(int i=0;i<n;i++){ //第i個元素分在第 i/len 塊
cin>>input;
//存入區間中
b[i/len].local.push_back(input);
//更新區間總和
b[i/len].global += input;
}
}
void update(long long q,long long v){
long long blk=q/len,i=q%len;
b[blk].global+=v-b[blk].local[i];
b[blk].local[i]=v;
return;
}
long long query(long long q){
long long rt=0,sum=0;
for(int i=0;i<num;++i){
sum+=b[i].global;
rt+=len;
if(sum>=q){
sum-=b[i].global;
rt-=len;
for(int j=0;j<len;++j){
sum+=b[i].local[j];
rt++;
if(sum>=q)return rt;
}
}
}
return -1;
}
char is;
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
build();
for(int i=0;i<m;++i){
cin >> is;
if(is=='2'){
cin >> x ;
long long ans=query(x);
if(ans==-1){
cout << "meh\n";
}
else{
cout << ans << '\n';
}
}
else{
cin >> x >> z;
update(x-1,z);
}
}
}