樹套樹裸題，練習模板的好去處。 注意每次SpLay修改前對原串的變動。
/************************************************************** PRoblem: 3196 User: vermouth Language: C++ Result: Accepted Time:8124 ms Memory:123440 kb****************************************************************/ #include<cstdio>#include<iostream>using namespace std;#define lson l,m,root<<1#define rson m+1,r,root<<1|1#define inf 0x3f3f3f3f const int maxn=250100; struct Splaytree{ int sz[maxn*20]; int ch[maxn*20][2]; int pre[maxn*20],rt[maxn<<2],top; inline void up(int x) { sz[x] = sz[ch[x][0]]+sz[ch[x][1]]+cnt[x]; } inline void rotate(int x,int f) { int y=pre[x]; ch[y][!f]=ch[x][f]; pre[ch[x][f]]=y; pre[x]=pre[y]; if(pre[x]) ch[pre[y]][ch[pre[y]][1]==y]=x; ch[x][f]=y; pre[y]=x; up(y); } inline void Splay(int x,int goal,int root) { while(pre[x]!=goal) { if(pre[pre[x]]==goal) rotate(x,ch[pre[x]][0]==x); else { int y=pre[x],z=pre[y]; int f=(ch[z][0]==y); if(ch[y][f]==x) rotate(x,!f),rotate(x,f); else rotate(y,f),rotate(x,f); } } up(x); if(goal==0) rt[root]=x; } inline void RTO(int k,int goal,int root) { int x=rt[root]; while(sz[ch[x][0]]!=k-1) { if(k<sz[ch[x][0]]+1) x=ch[x][0]; else { k-=(sz[ch[x][0]]+1); x=ch[x][1]; } } Splay(x,goal,root); } inline void Newnode(int &x,int c) { x=++top; ch[x][0]=ch[x][1]=pre[x]=0; sz[x]=1;cnt[x]=1; val[x]=c; } inline void init(){ top=0; } inline void Insert(int &x,int key,int f,int root){ if(!x){ Newnode(x,key); pre[x]=f; Splay(x,0,root); return ; } if(key==val[x]){ cnt[x]++; sz[x]++; return ; }else if(key<val[x]){ Insert(ch[x][0],key,x,root); }else{ Insert(ch[x][1],key,x,root); } up(x); } void Del(int root){ if(cnt[rt[root]]>1){ cnt[rt[root]]--; } else { int t=rt[root]; if(ch[rt[root]][1]){ rt[root]=ch[rt[root]][1]; RTO(1,0,root); ch[rt[root]][0]=ch[t][0]; if(ch[rt[root]][0]) pre[ch[rt[root]][0]]=rt[root]; } else rt[root]=ch[rt[root]][0]; pre[rt[root]]=0; } up(rt[root]); } void findkey(int x,int key,int &ans) { if(!x) return ; if(val[x]==key) ans=x; else if(val[x]>key) findkey(ch[x][0],key,ans); else findkey(ch[x][1],key,ans); } inline int find_kth(int x,int k,int root){ if(k<sz[ch[x][0]]+1){ return find_kth(ch[x][0],k,root); }else if(k>sz[ch[x][0]]+cnt[x]) return find_kth(ch[x][1],k-sz[ch[x][0]]-cnt[x],root); else { Splay(x,0,root); return val[x]; } } int findpre(int x,int z){ int ans=-inf; while(ch[x][val[x]<=z]) { if(val[x]<=z) ans=val[x]; x=ch[x][val[x]<=z]; }if(val[x]<=z) ans=max(ans,val[x]); return ans; } int findsuc(int x,int z){ int ans=inf; while(ch[x][val[x]<z]) { if(val[x]>=z) ans=val[x]; x=ch[x][val[x]<z]; }if(val[x]>=z) ans=min(ans,val[x]); return ans; } int val[maxn*20]; int cnt[maxn*20]; void build(int l,int r,int root) { rt[root]=0; for(int i=l;i<=r;i++) Insert(rt[root],a[i],0,root); if(l>=r) return ; int m=(l+r)>>1; build(lson); build(rson); } void update(int l,int r,int root,int i,int x) { int ans=0; findkey(rt[root],a[i],ans); Splay(ans,0,root); Del(root); Insert(rt[root],x,0,root); if(l>=r) return ; int m=(l+r)>>1; if(i<=m) update(lson,i,x); else update(rson,i,x); } int cntLess(int x,int key){ int ret=0; while(x) { if(val[x]>key) x=ch[x][0]; else { ret+=cnt[x]+sz[ch[x][0]]; x=ch[x][1]; } } return ret; } int getnumLess(int l,int r,int root,int L,int R,int x) { if(L<=l&&R>=r) { return cntLess(rt[root],x); } int m=(l+r)>>1; int ret=0; if(L<=m) ret+=getnumLess(lson,L,R,x); if(R>m) ret+=getnumLess(rson,L,R,x); return ret; } inline int get_pre(int l,int r,int root,int L,int R,int k) { if(L<=l&&R>=r) { return findpre(rt[root],k); } int ans=-inf; int m=(l+r)>>1; if(L<=m) ans=max(ans,get_pre(lson,L,R,k)); if(R>m) ans=max(ans,get_pre(rson,L,R,k)); return ans; } inline int get_suc(int l,int r,int root,int L,int R,int k) { if(L<=l&&R>=r) { return findsuc(rt[root],k); } int ans=inf;int m=(l+r)>>1; if(L<=m) ans=min(ans,get_suc(lson,L,R,k)); if(R>m) ans=min(ans,get_suc(rson,L,R,k)); return ans; } int search(int L,int R,int k) { int l=0,r=inf; int ans=0; while(l<=r) { int m=(l+r)>>1; int cnt=getnumLess(1,n,1,L,R,m); if(cnt>=k) { r=m-1;ans=m; } else l=m+1; } return ans; } void solve() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); for(int i=1;i<=m;i++) { int x,y,z,op; scanf("%d%d%d",&op,&x,&y);if(op!=3) scanf("%d",&z); if(op==1) printf("%d/n",getnumLess(1,n,1,x,y,z-1)+1); else if(op==2) printf("%d/n",search(x,y,z)); else if(op==3) update(1,n,1,x,y),a[x]=y; else if(op==4) printf("%d/n",get_pre(1,n,1,x,y,z-1)); else if(op==5) printf("%d/n",get_suc(1,n,1,x,y,z+1)); } } int a[maxn]; int n,m;} spt;int T; int main(){ spt.init(); spt.solve(); return 0;}/*30 10347297 7767863 4687361 4266761 1869189 6183125 6228737 7377798 2298221 253439 2279737 7603021 9596641 3461977 8857135 7648897 1264321 7381859 2257573 3750694 7066537 7631697 3115165 3367245 3742733 7943233 4901377 2381377 3162917 3567345 1 7 26 22982213 19 6712240 4 23 29 37431065 7 24 76247121 7 22 70665375 1 18 2518942 19 21 15 15 16 88557742 1 12 103 15 3539397 */新聞熱點
疑難解答
