正题

评测记录:/recordnew/lists?uid=SSL_WYC_zombieeeeee&pid=P3369&status=&sort=0

题目大意

要求支持查询一个数字的排名，查询该排名的数字，插入数字，删除数字，求前驱后继。

解题思路

Splay不解释。

codecodecode

#include<cstdio>#include<algorithm>#define INF 2100000000#define N 100010using namespace std;struct splay{int v[N],father[N];int l[N],r[N];int sum[N],recy[N];int n,points;#define root r[0]void Updata(int x){sum[x]=sum[l[x]]+sum[r[x]]+recy[x];}int Identify(int x){return l[father[x]]==x?0:1;}void Connect(int x,int f,int son){father[x]=f;if(son) r[f]=x;else l[f]=x;}void Rotate(int x){int y=father[x];int mroot=father[y];int mrootson=Identify(y);int yson=Identify(x);int B=(yson?l[x]:r[x]);Connect(B,y,yson);Connect(y,x,(yson^1));Connect(x,mroot,mrootson);Updata(y);Updata(x);}void Splay(int at,int to){to=father[to];while(father[at]!=to){int up=father[at];if(father[up]==to) Rotate(at);else if(Identify(up)==Identify(at)){Rotate(up);Rotate(at);}else{Rotate(at);Rotate(at);}}}int CrePoint(int vs,int fathers){n++;v[n]=vs;father[n]=fathers;sum[n]=recy[n]=1;return n;}void Destory(int x){v[x]=l[x]=r[x]=sum[x]=father[x]=recy[x]=0;if(x==n)n--;}int getroot(){return root;}int FindVal(int vs){int now=root;if(!now) return 0;while(true){if(v[now]==vs){Splay(now,root);return root;}int next=vs<v[now]?0:1;if(!(next?r[now]:l[now])) return 0;now=(next?r[now]:l[now]);}}int Build(int vs){points++;if(!n){root=1;CrePoint(vs,0);}else{int now=root;while(1){sum[now]++;if(vs==v[now]){recy[now]++;return now;}int next=vs<v[now]?0:1;if(!(next?r[now]:l[now])){CrePoint(vs,now);if(next) r[now]=n;else l[now]=n;return n;}now=next?r[now]:l[now];}}return 0;}void Insert(int vs){int add=Build(vs);Splay(add,root);}void Remove(int vs){int deal=FindVal(vs);if(!deal) return;points--;if(recy[deal]>1){recy[deal]--;sum[deal]--;return;}if(!l[deal]){root=r[deal];father[root]=0;}else{int lef=l[deal];while(r[lef]) lef=r[lef];Splay(lef,l[deal]);int rig=r[deal];Connect(rig,lef,1);Connect(lef,0,1);Updata(lef);}Destory(deal);}int GetRankByVal(int vs){int now=root;if(!now) return 0;while((vs>v[now]?r[now]:l[now])&&vs!=v[now])now=(vs>v[now]?r[now]:l[now]);Splay(now,root);return sum[l[root]];}int GetValByRank(int x){if(x>points) return -INF;int now=root;while(1){int minused=sum[now]-sum[r[now]];if(x>sum[l[now]]&&x<=minused) break;if(x<minused)now=l[now];else{x-=minused;now=r[now];}}Splay(now,root);return v[now];}int Upper(int vs){int now=root;int result=INF;while(now){if(v[now]>vs&&v[now]<result) result=v[now];if(vs<v[now]) now=l[now];else now=r[now];}return result;}int Lower(int vs){int now=root;int result=-INF;while(now){if(v[now]<vs&&v[now]>result) result=v[now];if(vs>v[now]) now=r[now];else now=l[now];}return result;}#undef root}a;int main(){freopen("testdata.in","r",stdin);freopen("data.out","w",stdout);a.Insert(-INF);a.Insert(INF);int m;scanf("%d",&m);while(m--){int opt,x;scanf("%d%d",&opt,&x);if(opt==1) a.Insert(x);if(opt==2) a.Remove(x);if(opt==3) printf("%d\n",a.GetRankByVal(x));if(opt==4) printf("%d\n",a.GetValByRank(x+1));if(opt==5) printf("%d\n",a.Lower(x));if(opt==6) printf("%d\n",a.Upper(x));}}