P2617 Dynamic Rankings

題意:

待修改的區(qū)間最值問題

題解：

整體二分天然帶有修改性
整體二分做不帶修改的區(qū)間最值—>看這里
現(xiàn)在待修改，我們可以將第l位修改為x，因?yàn)槲覀兪怯脴錉顢?shù)組來維護(hù)的，所以把這個過程拆分成將第l個數(shù)刪去，再將第l個數(shù)加上，但是這兩個第l數(shù)所指的值是不一樣的，因?yàn)槲覀兪桥袛?#xff0c;只有值<=mid的數(shù)才插入到樹狀數(shù)組中，雖然是同一個位置，但是因?yàn)榭赡芨牧酥祵?dǎo)致原本插入，現(xiàn)在不插入，也有可能相反，這樣就實(shí)現(xiàn)了修改操作，其實(shí)還是要把整體二分的原理搞清楚就懂了
比如：當(dāng)然mid = 3
第L位原本是2現(xiàn)在改成4
一開始第L位是插入到樹狀數(shù)組的（因?yàn)?<mid）（讀入數(shù)據(jù)時的操作），然后先將第L位刪去（修改操作分離出的刪去操作），然后判斷現(xiàn)在值是否滿足要求，發(fā)現(xiàn)不滿足(4>mid=3)，則不插入到樹狀數(shù)組，這樣一套，就完成了修改

代碼：

#pragma optimize("Ofast") #include<bits/stdc++.h> #define MAXN 300005 #define inf int(1e9) using namespace std; typedef long long ll;int N,M; int a[MAXN];struct Node{int op,x,y,k;//op=insert+1/remove-1,query2int id;Node(int op=0, int x=0, int y=0, int k=0, int id=0):op(op), x(x), y(y), k(k), id(id){} } q[MAXN],lq[MAXN],rq[MAXN];// int fw[MAXN]; inline int lbt(int x){return x&(-x); }inline void change(int x, int dv){for(;x<=N;x+=lbt(x)){fw[x] += dv;} }inline int query(int x){int ans = 0;for(;x>0;x-=lbt(x)){ans += fw[x];}return ans; } // int ANS[MAXN];void solve(int vl, int vr, int ql, int qr){//cerr<<"solve: "<<vl<<" "<<vr<<" "<<ql<<" "<<qr<<endl;if(ql > qr) return;if(vl == vr){for(int i=ql;i<=qr;i++){if(q[i].op==2) ANS[q[i].id] = vl;}return;}//insertint mid = (vl + vr)>>1;int nl = 0, nr = 0;for(int i=ql;i<=qr;i++){if(q[i].op != 2){//insert/removeif(q[i].x <= mid) change(q[i].y, q[i].op), lq[++nl] = q[i];else rq[++nr] = q[i];}else{//queryint n = query(q[i].y) - query(q[i].x-1);if(q[i].k <= n) lq[++nl] = q[i];else{q[i].k -= n;rq[++nr] = q[i];}}}//removefor(int i=ql;i<=qr;i++){if(q[i].op != 2){if(q[i].x <= mid) change(q[i].y, -q[i].op);}}for(int i=1;i<=nl;i++) q[ql+i-1] = lq[i];for(int i=1;i<=nr;i++) q[ql+nl+i-1] = rq[i];solve(vl, mid, ql, ql+nl-1);solve(mid+1, vr, ql+nl, qr); }int main(){scanf("%d%d", &N, &M);int NN = 0, Q = 0; int x,l,r,k;for(int i=1;i<=N;++i){scanf("%d", &a[i]);q[++NN] = Node(1,a[i],i);}char op[5];for(int i=1;i<=M;i++){scanf("%s", op);if(op[0]=='Q'){scanf("%d%d%d", &l, &r, &k);q[++NN] = Node(2,l,r,k,++Q);} else{scanf("%d%d", &l, &x);q[++NN] = Node(-1,a[l],l);q[++NN] = Node(+1,x,l);a[l] = x;}}solve(-1e9,1e9,1,NN);for(int i=1;i<=Q;i++){printf("%d\n", ANS[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P2617 Dynamic Rankings(整体二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。