treap（bzoj3224）
#include<cstring> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstdio> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 200500 using namespace std; int n,op,root,ans,x; struct T{ int l[maxn],r[maxn],s[maxn],v[maxn],w[maxn],rnd[maxn]; int cnt; void up(int t){ s[t]=s[l[t]]+s[r[t]]+w[t]; } void rt(int &t){ int k=l[t]; l[t]=r[k]; r[k]=t; up(t); up(k); t=k; } void lt(int &t){ int k=r[t]; r[t]=l[k]; l[k]=t; up(t); up(k); t=k; } void insert(int &t,int x){ if (t==0){ t=++cnt; v[t]=x; s[t]=w[t]=1; rnd[t]=rand(); return; } s[t]++; if (x==v[t]) w[t]++; else if (x<v[t]) { insert(l[t],x); if (rnd[l[t]]<rnd[t]) rt(t); } else { insert(r[t],x); if (rnd[r[t]]<rnd[t]) lt(t); } } void del(int &t,int x){ if (t==0) return; if (x==v[t]){ if (w[t]>1) {w[t]--; s[t]--;return;} //!!!!!!!!!!!! if (l[t]*r[t]==0) t=l[t]+r[t]; else if (rnd[l[t]]<rnd[r[t]]) rt(t),del(t,x); else lt(t),del(t,x); } else if (x<v[t]) s[t]--,del(l[t],x); else s[t]--,del(r[t],x); } int rank(int t,int x){ if (t==0) return 0; if (x==v[t]) return s[l[t]]+1; else if (x<v[t]) return rank(l[t],x); else return s[l[t]]+w[t]+rank(r[t],x); } int select(int t,int k){ if (t==0) return 0; if (k>=s[l[t]]+1&&k<=s[l[t]]+w[t]) return v[t]; else if (k<s[l[t]]+1) return select(l[t],k); else return select(r[t],k-s[l[t]]-w[t]); } void pred(int t,int x){ if (t==0) return; if (v[t]<x){ ans=v[t]; pred(r[t],x); } else pred(l[t],x); } void succ(int t,int x){ if (t==0) return ; if (v[t]>x){ ans=v[t]; succ(l[t],x); } else succ(r[t],x); } }treap; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } int main(){ // freopen("in.txt","r",stdin); n=read(); rep(i,1,n){ op=read(); if (op==1) {x=read(); treap.insert(root,x);} if (op==2) {x=read(); treap.del(root,x);} if (op==3) {x=read(); printf("%d ",treap.rank(root,x));} if (op==4) {x=read(); printf("%d ",treap.select(root,x));} if (op==5) {x=read(); ans=0; treap.pred(root,x); printf("%d ",ans);} if (op==6) {x=read(); ans=0; treap.succ(root,x); printf("%d ",ans);} } return 0; }