#53645: 有趣的照樣照句 (外加程式加思路)
Tino961009
(能AC，就別管怎麼AC)
學校
:
國立臺中第二高級中學
編號 : 288138
來源 : [111.82.100.143]
最後登入時間 ：
2025-10-11 12:15:02
這下他慘了，程式碼全部被刪除了，又沒有存檔，於是他回到ZeroJudge，想要繼續刷題目。看到他一回來，所有寫程式的人便都看著他笑，有的叫道，「雨天(角色名)，你怎麼又忘記存檔了！」他不回答，對CXXT GPT說，「給我一份完整的程式碼。」他們又故意的高聲嚷道，「你一定又抄AI的程式了！」雨天睜大眼睛說，「你怎麼這樣憑空汙人清白……」「什麼清白？我前天親眼見你抄，還訂閱CXXT Plus。」攗皥蒽便漲紅了臉，額上的青筋條條綻出，爭辯道，「借鑒不能算抄……抄！…… 工程師的事，能算抄嗎？」接連便是難懂的話，什麼「怎麼又TLE」，什麼「Binary Index Tree 加上 Binary search 好麻煩」之類的，引得眾人都哄笑起來：討論區內外充滿了快活的空氣。
註！！：本人沒借鑑 真的
用Binary Index Tree(BIT) 儲存 BIT [ i ] 儲存 i - i&-i 到 i 的總和 有點像 prefix
再用 二分搜找到符合的最小值
雖然很長但寫完很有成就感喔
底下附程式碼(反白)
#include<bits/stdc++.h>
using namespace std;
vector<long long> c(1,0), f(1,0);
int n;
long long query(int id){
long long sum=0;
while(id>0){
sum+=f[id];
id-=(id&-id);
}
return sum;
}
void binary_search(int l, int r, int g){
if(query(r)<g&&r==n){
cout<<"meh"<<endl;
return;
}
if(query(l)>=g&&l==1){
cout<<l<<endl;
return;
}
if(r==l+1){
cout<<r<<endl;
return;
}
int mid=(r+l)/2;
if(query(mid)>=g) binary_search(l, mid, g);
else binary_search(mid, r, g);
}
void change(int id, int m){
int C=m-c[id];
c[id]=m;
while(id<=n){
f[id]+=C;
id+=(id&-id);
}
}
void index(int id, int m){
while(id<=n){
f[id]+=m;
id+=(id&-id);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m, d, t, g;
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>d;
c.push_back(d);
f.push_back(0);
}
for(int i=1; i<=n; i++) index(i, c[i]);
for(int i=1; i<=m; i++){
cin>>t;
if(t==2){
cin>>g;
binary_search(1, n, g);
}
else{
cin>>t>>g;
change(t, g);
}
}
return 0;
}