bzoj3224 普通平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

Input

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数，表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

Hint

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

题解

　　如题，随便用个平衡树维护即可。（我用的是Splay）

Code

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cmath>
  7 using namespace std;
  8 #define ll long long
  9 #define REP(i,a,b) for(register int i=(a),_end_=(b);i<=_end_;i++)
 10 #define DREP(i,a,b) for(register int i=(a),_end_=(b);i>=_end_;i--)
 11 #define EREP(i,a) for(register int i=start[(a)];i;i=e[i].next)
 12 inline int read()
 13 {
 14     int sum=0,p=1;char ch=getchar();
 15     while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
 16     if(ch=='-')p=-1,ch=getchar();
 17     while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
 18     return sum*p;
 19 }
 20 
 21 const int maxn=3e5+20;
 22 
 23 struct node {
 24     int cnt,val,ch[2],fa,sz;//每个节点维护两个信息，该点所代表的值和以该点为根的树的节点个数，cnt表示是这个值的数的个数
 25 };
 26 node t[maxn];
 27 int n,root=0,sz;
 28 
 29 void init()
 30 {
 31     n=read();
 32 }
 33 
 34 void push_up(int u)//维护以u点为根的树的节点个数
 35 {
 36     t[u].sz=t[t[u].ch[0]].sz+t[t[u].ch[1]].sz+t[u].cnt;
 37 }
 38 
 39 void rotate(int x)
 40 {
 41     int y=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x;
 42     t[z].ch[t[z].ch[1]==y]=x;t[x].fa=z;
 43     t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].fa=y;
 44     t[x].ch[k^1]=y;t[y].fa=x;push_up(y);push_up(x);
 45 }
 46 
 47 void Splay(int x,int goal)
 48 {
 49     while(t[x].fa!=goal)
 50     {
 51         int y=t[x].fa,z=t[y].fa;
 52         if(t[y].fa!=goal)
 53         {
 54             ((t[y].ch[0]==x)^(t[z].ch[0]==y))?rotate(x):rotate(y);
 55         }
 56         rotate(x);
 57     }
 58     if(!goal)root=x;
 59 }
 60 
 61 void newt(int fa,int id,int val)
 62 {
 63     t[id]={1,val,{0,0},fa,1};
 64 }
 65 
 66 void insert(int x)
 67 {
 68     int u=root,fa=0;
 69     while(u && t[u].val!=x){fa=u;u=t[u].ch[x>t[u].val];}
 70     if(u)t[u].cnt++;
 71     else
 72     {
 73         u=++sz;
 74         if(fa)t[fa].ch[x>t[fa].val]=u;
 75         newt(fa,sz,x);
 76     }
 77     Splay(u,0);
 78 }
 79 
 80 void Find(int x)
 81 {
 82     int u=root;if(!u)return;
 83     while(t[u].ch[x>t[u].val] && x!=t[u].val)
 84     {
 85         u=t[u].ch[x>t[u].val];
 86     }
 87     Splay(u,0);
 88 }
 89 
 90 int Nxt(int x,int f)//求前驱和后继
 91 {
 92     Find(x);
 93     int u=root;
 94     if((t[u].val>x && f)|| (t[u].val<x && !f))return u;
 95     u=t[u].ch[f];
 96     while(t[u].ch[f^1])u=t[u].ch[f^1];
 97     return u;
 98 }
 99 
100 void Del(int x)//找出前驱和后继后，把前驱变成根，后继变成根的右儿子，要删除的点就是后继的左儿子
101 {
102     int last=Nxt(x,0),next=Nxt(x,1);
103     Splay(last,0);Splay(next,last);
104     int del=t[next].ch[0];
105     if(t[del].cnt>1)t[del].cnt--,Splay(del,0);
106     else t[next].ch[0]=0;
107 }
108 
109 int kth(int x)
110 {
111     int u=root;
112     if(t[u].sz<x)return 0;
113     while(1)
114     {
115         int y=t[u].ch[0];
116         if(x>t[y].sz+t[u].cnt)
117         {
118             x-=t[y].sz+t[u].cnt;
119             u=t[u].ch[1];
120         }
121         else if(t[y].sz>=x)
122             u=y;
123         else
124             return t[u].val;
125     }
126 }
127 
128 void doing()
129 {
130     insert(-0x7fffffff); insert(0x7fffffff);//必须要在两边加个点，不然可能找不到前驱或后继
131     REP(i,1,n)
132     {
133         int opt=read(),x=read();
134         if(opt==1)
135         {
136             insert(x);
137         }
138         else if(opt==2)
139         {
140             Del(x);
141         }
142         else if(opt==3)
143         {
144             Find(x);
145             cout<<t[t[root].ch[0]].sz<<endl;//前面加了一个点，所以计算排名要减去1
146         }
147         else if(opt==4)
148         {
149             cout<<kth(x+1)<<endl;//同理，在查找排名时要加1
150         }
151         else if(opt==5)
152         {
153             cout<<t[Nxt(x,0)].val<<endl;
154         }else
155         {
156             cout<<t[Nxt(x,1)].val<<endl;
157         }
158     }
159 }
160 
161 int main()
162 {
163     init();
164     doing();
165     return 0;
166 }