P2617 Dynamic Rankings
帶修改主席樹
能進行對序列中數進行修改

#include<iostream> #include<string.h> #include<stdio.h> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<set> #include<stack> #include<map> using namespace std; #define ll long long const int mx=2e5+7; int m,n,a[mx],b[mx]; struct ZXtree{int rt[mx],lc[mx<<9],rc[mx<<9],sz[mx<<9]; rt根節點，sz 序列中某個數的個數int node_sz,lnum[mx],rnum[mx],lsz,rsz;void init(){node_sz=0;lsz=rsz=0;}void add(int &o,int l,int r,int k,int num){if(!o) o=++node_sz;sz[o]+=num;if(l==r) return;int mid=(l+r)>>1;if(k<=mid) add(lc[o],l,mid,k,num);else add(rc[o],mid+1,r,k,num);}void update(int x,int len,int cn){int k=lower_bound(b+1,b+len+1,a[x])-b;while(x<=n){add(rt[x],1,len,k,cn);x+=x&(-x);}}int query(int l,int r,int kth){if(l==r) return l;int sum=0;for(int i=1;i<=rsz;i++) sum+=sz[lc[rnum[i]]];for(int i=1;i<=lsz;i++) sum-=sz[lc[lnum[i]]];int mid=(l+r)>>1;if(kth<=sum){for(int i=1;i<=rsz;i++) rnum[i]=lc[rnum[i]];for(int i=1;i<=lsz;i++) lnum[i]=lc[lnum[i]];return query(l,mid,kth);}else{for(int i=1;i<=rsz;i++) rnum[i]=rc[rnum[i]];for(int i=1;i<=lsz;i++) lnum[i]=rc[lnum[i]];return query(mid+1,r,kth-sum);}} }zxt; struct node{char c;int l,r;int k; }ts[mx];int main() {int cnt=0;cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}cnt=n;for(int i=1;i<=m;i++){scanf(" %c%d%d",&ts[i].c,&ts[i].l,&ts[i].r);if(ts[i].c=='Q') scanf("%d",&ts[i].k);else b[++cnt]=ts[i].r;}sort(b+1,b+cnt+1);cnt=unique(b+1,b+cnt+1)-b-1;zxt.init();for(int i=1;i<=n;i++) zxt.update(i,cnt,1);for(int i=1;i<=m;i++){if(ts[i].c=='C'){zxt.update(ts[i].l,cnt,-1);a[ts[i].l]=ts[i].r;zxt.update(ts[i].l,cnt,1);}else{zxt.lsz=zxt.rsz=0;for(int j=ts[i].l-1;j>0;j-=j&(-j)) zxt.lnum[++zxt.lsz]=zxt.rt[j];for(int j=ts[i].r;j>0;j-=j&(-j)) zxt.rnum[++zxt.rsz]=zxt.rt[j];printf("%d\n",b[zxt.query(1,cnt,ts[i].k)]);}}return 0; }

總結

以上是生活随笔為你收集整理的P2617 Dynamic Rankings（带修改主席树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。