(其实今天好热啊?
题目大意:插入,删除,k小,前驱后继,数的排名。
splay和treap裸题...过几天补个treap的
splay:
#include#include #include #include #define which(x) (son[fa[x]][1]==x)using namespace std;const int extar[2]={ 2147483647,-2147483647};int fa[100010],count[100010],son[100010][3],val[100010],data[100010];int root,x,y,n,tot,xiugai;void read(int &k){ k=0;int f=1;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f;}void rotate(int x){ int f=fa[x]; bool k=which(x); son[f][k]=son[x][!k];son[x][!k]=f;son[fa[f]][which(f)]=x; if(son[f][k])fa[son[f][k]]=f;fa[x]=fa[f];fa[f]=x; count[x]=count[f]; count[f]=count[son[f][0]]+count[son[f][1]]+val[f];}void splay(int x,int g){ while(fa[x]!=g) { int f=fa[x]; if(fa[f]==g) { rotate(x); break; } if(which(x)^which(f))rotate(x); else rotate(f); rotate(x); } if(!g)root=x;}int search(int x,int y){ if(data[x]>y&&son[x][0])return search(son[x][0],y); if(data[x] x)return data[k]; return ext(son[k][1],1);}int rank(int x,int k){ if(k<=count[son[x][0]])return rank(son[x][0],k); if(k<=(count[son[x][0]]+val[x]))return x; return rank(son[x][1],k-count[son[x][0]]-val[x]);}int findnum(int x){ int k=search(root,x); splay(k,0); return count[son[k][0]]+1;}void insert(int &x,int w,int f){ if(!x) { x=++tot; count[x]=val[x]=1; data[x]=w; fa[x]=f; xiugai=tot; return; } if(data[x]==w)val[x]++,xiugai=x; if(data[x] w)insert(son[x][0],w,x); count[x]++;}void del(int w){ int k=search(root,w); splay(k,0); if(data[k]==w) { if(val[k]>1)val[k]--,count[k]--; else if(!son[k][0]) { root=son[k][1]; fa[root]=fa[k]=son[k][1]=count[k]=val[k]=data[k]=0; } else { fa[son[k][0]]=0;ext(son[k][0],0); son[root][1]=son[k][1]; if(son[k][1])fa[son[k][1]]=root; count[root]+=count[son[k][1]]; fa[k]=son[k][0]=son[k][1]=data[k]=val[k]=count[k]=0; } }}int main(){ read(n); for(int i=1;i<=n;i++) { read(x);read(y); switch(x) { case 1:insert(root,y,0);splay(xiugai,0);root=xiugai;break; case 2:del(y);break; case 3:printf("%d\n",findnum(y));break; case 4:printf("%d\n",data[rank(root,y)]);break; case 5:printf("%d\n",pred(y));break; case 6:printf("%d\n",succ(y));break; default:break; } }}