這個(gè)有點(diǎn)復(fù)雜，按理應(yīng)該寫(xiě)寫(xiě)的……下次再說(shuō)吧

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct node {int l,r,sum;#define l(x) tr[x].l#define r(x) tr[x].r#define sum(x) tr[x].sum }tr[10000000]; struct que {char a;int l,r,kth; }qq[20010];int cnt,m,ce,T[20010],S[20010]; int n,Q,a[20010],b[20010]; int use[3][20010];inline int lowbit(int x){return x&(-x);} inline int build(int l,int r) {int now=++cnt;if(l==r)return now;int mid=(l+r)>>1;l(now)=build(l,mid);r(now)=build(mid+1,r);return now; } inline int build_new(int flag,int mark,int loc,int val) {int rt=++cnt;int before;if(mark==1)before=T[0];else before=flag?T[mark-1]:S[mark-1];if(!flag && val) before=S[mark];sum(rt)=sum(before)+val;int l=1,r=m,now=rt,still=before,mid;for(;l(still)||r(still);){mid=(l+r)>>1;if(loc>mid){l(now)=l(still);r(now)=++cnt;sum(cnt)=sum(r(still))+val;now=cnt;still=r(still);l=mid+1;}else{r(now)=r(still);l(now)=++cnt;sum(cnt)=sum(l(still))+val;now=cnt;still=l(still);r=mid;}}return rt; } inline void updata(int loc,int num) {int where;where=lower_bound(b+1,b+m+1,a[loc])-b;for(int i=loc;i<=n;i+=lowbit(i))S[i]=build_new(0,i,where,-1);where=lower_bound(b+1,b+m+1,num)-b;for(int i=loc;i<=n;i+=lowbit(i))S[i]=build_new(0,i,where,1);a[loc]=num; } int Sum(int y,int x) {int res=0;for(int i=x;i>=1;i-=lowbit(i))res+=sum(l(use[y][i]));return res; } int ask(int u,int v,int a,int b,int l,int r,int k) {if(l==r)return l;int lm=Sum(2,v)+sum(l(b))-sum(l(a))-Sum(1,u),mid=(l+r)>>1;if(k<=lm){for(int i=u;i>=1;i-=lowbit(i))use[1][i]=l(use[1][i]);for(int i=v;i>=1;i-=lowbit(i))use[2][i]=l(use[2][i]);return ask(u,v,l(a),l(b),l,mid,k);}else{for(int i=u;i>=1;i-=lowbit(i))use[1][i]=r(use[1][i]);for(int i=v;i>=1;i-=lowbit(i))use[2][i]=r(use[2][i]);return ask(u,v,r(a),r(b),mid+1,r,k-lm);} } signed main() {cin>>n>>Q;ce=n;for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];for(int i=1;i<=Q;i++){cin>>qq[i].a>>qq[i].l>>qq[i].r;if(qq[i].a=='Q')cin>>qq[i].kth;else b[++ce]=qq[i].r;}sort(b+1,b+ce+1);m=unique(b+1,b+ce+1)-b-1;T[0]=build(1,m);for(int i=1;i<=n;i++){int loc=lower_bound(b+1,b+m+1,a[i])-b;T[i]=build_new(1,i,loc,1);}for(int i=1;i<=n;i++)S[i]=build_new(0,i,1,0);for(int i=1;i<=Q;i++){if(qq[i].a=='Q'){int x=qq[i].l,y=qq[i].r;for(int j=x-1;j>=1;j-=lowbit(j))use[1][j]=S[j];for(int j=y;j>=1;j-=lowbit(j))use[2][j]=S[j]; printf("%ld\n",b[ask(x-1,y,T[x-1],T[y],1,m,qq[i].kth)]);}else updata(qq[i].l,qq[i].r);} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Al-Ca/p/11022660.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的模板—主席树（待修改）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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