3224: Tyvj 1728 普通平衡树（新板子）

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 17048 Solved: 7429
[Submit][Status][Discuss]

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.每个数的数据范围：[-2e9,2e9]

code

2018-07-01

  1 #include<cstdio>
  2 #include<cctype>
  3 
  4 const int N = 1000100;
  5 
  6 int siz[N],ch[N][2],fa[N],cnt[N],data[N];
  7 int Root,tn;
  8 
  9 #define ls ch[p][0]
 10 #define rs ch[p][1]
 11 
 12 int son(int x) {
 13     return x==ch[fa[x]][1];
 14 }
 15 void pushup(int p) {
 16     siz[p] = siz[ls] + siz[rs] + cnt[p];
 17 }
 18 void rotate(int x) {
 19     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 20     if (z) ch[z][c] = x;else Root = x;fa[x] = z;
 21     ch[x][!b] = y;fa[y] = x;
 22     ch[y][b] = a;if (a) fa[a] = y;
 23     pushup(y),pushup(x);
 24 }
 25 void splay(int x,int rt) {
 26     while (fa[x] != rt) {
 27         int y = fa[x],z = fa[y];
 28         if (z==rt) rotate(x);
 29         else {
 30             if (son(x)==son(y)) rotate(y),rotate(x);
 31             else rotate(x),rotate(x); 
 32         }
 33     }
 34 }
 35 int getrnk(int x) {
 36     int p = Root,ans = 0;
 37     while (true) {
 38         if (!p) return ans + 1;
 39         if (x == data[p]) {ans += siz[ls];splay(p,0);return ans+1;}
 40         if (x < data[p]) p = ls;
 41         else { 
 42             ans += siz[ls] + cnt[p];
 43             p = rs;
 44         }
 45     }
 46 }
 47 int getkth(int k) {
 48     int p = Root;
 49     while (true) {
 50         if (siz[ls] < k && k <= siz[ls] + cnt[p]) return data[p];
 51         if (k <= siz[ls]) p = ls;
 52         else {
 53             k -= siz[ls] + cnt[p]; 
 54             p = rs; 
 55         }
 56     }
 57 }
 58 int Newnode(int pa,int d) {
 59     ++tn;siz[tn] = cnt[tn] = 1;ch[tn][1] = ch[tn][0] = 0;
 60     data[tn] = d;fa[tn] = pa;
 61     return tn;
 62 }
 63 void Insert(int x) {
 64     if (!Root) {Root = Newnode(0,x);return ;}
 65     int p = Root,pa = 0;
 66     while (true) {
 67         if (data[p]==x) {
 68             cnt[p] ++;pushup(p);pushup(pa);splay(p,0);return ; // Splay ????????????????? 
 69         }
 70         pa = p; // ??! 
 71         p = ch[p][x > data[p]];
 72         if (!p) {
 73             p = Newnode(pa,x);
 74             ch[pa][x > data[pa]] = p;
 75             pushup(p),pushup(pa);splay(p,0);
 76             break; 
 77         }
 78     }
 79 }
 80 void Clear(int p) {
 81     siz[p] = cnt[p] = ch[p][0] = ch[p][1] = fa[p] = data[p] = 0;
 82 }
 83 void Delete(int x) {
 84     getrnk(x);
 85     int &p = Root,tmp;
 86     if (cnt[p]) {cnt[p]--;pushup(p);return ;}
 87     if (!ls && !rs) {Clear(p);Root = 0;return ;}
 88     if (!ls || !rs) {tmp = p;p = ls?ls:rs;fa[p] = 0;Clear(tmp);return ;}
 89     int pre = ls;
 90     while (ch[pre][1]) pre = ch[pre][1];
 91     tmp = p;p = pre;
 92     splay(p,0);
 93     ch[p][1] = ch[tmp][1];fa[ch[tmp][1]] =  p;
 94     Clear(tmp);pushup(p);
 95 }
 96 int main() {
 97     int T,opt,x;
 98     scanf("%d",&T);
 99     while (T--) {
100         scanf("%d%d",&opt,&x);
101         if (opt==1) Insert(x);
102         else if (opt==2) Delete(x);
103         else if (opt==3) printf("%d
",getrnk(x));
104         else if (opt==4) printf("%d
",getkth(x));
105         else if (opt==5) printf("%d
",getkth(getrnk(x)-1)); 
106         else printf("%d
",getkth(getrnk(x+1)));
107     } 
108 }

View Code

持续更新2018-05-02

  1 #include<cstdio>
  2 #include<cctype>
  3 
  4 const int N = 1000100;
  5 
  6 int siz[N],ch[N][2],fa[N],cnt[N],data[N];
  7 int Root,tn;
  8 
  9 #define ls ch[p][0]
 10 #define rs ch[p][1]
 11 
 12 int son(int x) {
 13     return x==ch[fa[x]][1];
 14 }
 15 void pushup(int p) {
 16     siz[p] = siz[ls] + siz[rs] + cnt[p];
 17 }
 18 void rotate(int x) {
 19     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 20     if (z) ch[z][c] = x;else Root = x;fa[x] = z;
 21     ch[x][!b] = y;fa[y] = x;
 22     ch[y][b] = a;if (a) fa[a] = y;
 23     pushup(y),pushup(x);
 24 }
 25 void splay(int x,int rt) {
 26     while (fa[x] != rt) {
 27         int y = fa[x],z = fa[y];
 28         if (z==rt) rotate(x);
 29         else {
 30             if (son(x)==son(y)) rotate(y),rotate(x);
 31             else rotate(x),rotate(x); 
 32         }
 33     }
 34 }
 35 int getrnk(int k) {
 36     int p = Root,ans = 0;
 37     while (true) {
 38         if (!p) return ans + 1; // 没有这个点 
 39         if (k < data[p]) p = ls;
 40         else { 
 41             ans += (ls?siz[ls]:0);
 42             if (k == data[p]) {
 43                 splay(p,0);return ans + 1;
 44             }
 45             ans += cnt[p];
 46             p = rs;
 47         } 
 48     }
 49 }
 50 int getkth(int k) {
 51     int p = Root;
 52     while (true) {
 53         if (k <= siz[ls]) p = ls;
 54         else {
 55             k -= ls?siz[ls]:0;
 56             if (k<=cnt[p]) return data[p];
 57             k -= cnt[p];
 58             p = rs;
 59         }
 60     } 
 61 }
 62 int Newnode(int pa,int d) {
 63     ++tn;siz[tn] = cnt[tn] = 1;ch[tn][1] = ch[tn][0] = 0;
 64     data[tn] = d;fa[tn] = pa;
 65     return tn;
 66 }
 67 void Insert(int x) {
 68     if (!Root) {Root = Newnode(0,x);return ;}
 69     int p = Root,pa = 0;
 70     while (true) {
 71         if (data[p]==x) {
 72             cnt[p] ++;pushup(p);pushup(pa);splay(p,0);return ; // Splay 为了更新新新加入节点后产生的变化。 
 73         }
 74         pa = p; // 顺序！ 
 75         p = ch[p][x > data[p]];
 76         if (!p) {
 77             p = Newnode(pa,x);
 78             ch[pa][x > data[pa]] = p;
 79             pushup(p),pushup(pa);splay(p,0);
 80             break; 
 81         }
 82     }
 83 }
 84 void Clear(int p) {
 85     siz[p] = cnt[p] = ch[p][0] = ch[p][1] = fa[p] = data[p] = 0;
 86 }
 87 void Delete(int x) {
 88     getrnk(x);
 89     int &p = Root,tmp;
 90     if (cnt[p]) {cnt[p]--;pushup(p);return ;}
 91     if (!ls && !rs) {Clear(p);Root = 0;return ;}
 92     if (!ls || !rs) {tmp = p;p = ls?ls:rs;fa[p] = 0;Clear(tmp);return ;}
 93     int pre = ls;
 94     while (pre) pre = ch[pre][1];
 95     tmp = p;p = pre;
 96     splay(p,0);
 97     ch[p][1] = ch[tmp][1];fa[ch[tmp][1]] =  p;
 98     Clear(tmp);pushup(p);
 99 }
100 int main() {
101     int T,opt,x;
102     scanf("%d",&T);
103     while (T--) {
104         scanf("%d%d",&opt,&x);
105         if (opt==1) Insert(x);
106         else if (opt==2) Delete(x);
107         else if (opt==3) printf("%d
",getrnk(x));
108         else if (opt==4) printf("%d
",getkth(x));
109         else if (opt==5) printf("%d
",getkth(getrnk(x)-1)); 
110         else printf("%d
",getkth(getrnk(x+1)));
111     } 
112 }

View Code

再一次更新2018-05-01

  1 #include<cstdio>
  2 #include<cctype>
  3 
  4 const int N = 100010;
  5 int fa[N],ch[N][2],siz[N],cnt[N],data[N];
  6 int tn,Root;
  7 
  8 inline int read() {
  9     int x = 0,f = 1;char ch = getchar();
 10     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
 11     for (; isdigit(ch); ch=getchar()) x = x*10+ch-'0';
 12     return x * f; 
 13 }
 14 #define ls ch[p][0]
 15 #define rs ch[p][1]
 16 inline int son(int x) {
 17     return x == ch[fa[x]][1]; // - 
 18 }
 19 inline void pushup(int x) {
 20     siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
 21 }
 22 void rotate(int x) {
 23     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 24     if (z) ch[z][c] = x;else Root = x;fa[x] = z; // 调整x的位置
 25     ch[x][!b] = y;fa[y] = x; // 调整y的位置
 26     ch[y][b] = a;if (a) fa[a] = y; // 给y另一个子节点
 27     pushup(y);pushup(x);
 28 }
 29 void splay(int x,int rt) {
 30     while (fa[x] != rt) {
 31         int y = fa[x],z = fa[y];
 32         if (z==rt) rotate(x);
 33         else {
 34             if (son(x)==son(y)) rotate(y),rotate(x);
 35             else rotate(x),rotate(x);
 36         }
 37     }
 38 }
 39 int getrnk(int k) { // 得到k的排名,位置 
 40     int p = Root,ans = 0;
 41     while (true) {
 42         if (p == 0) return ans + 1;
 43         if (k < data[p]) p = ls;
 44         else {
 45             ans += (ls ? siz[ls] : 0);
 46             if (k==data[p]) {
 47                 splay(p,0);return ans+1;
 48             }
 49             ans += cnt[p];
 50             p = rs;
 51         }
 52     }
 53 }
 54 int getkth(int k) { // 得到第k个数
 55     int p = Root;
 56     while (true) {
 57         if (ls && k <= siz[ls]) p = ls;
 58         else {
 59             int tmp = (ls ? siz[ls] : 0) + cnt[p];
 60             if (k <= tmp) return data[p];
 61             k -= tmp; p = rs;
 62         }
 63     }
 64 }
 65 void newnode(int x,int pa,int d) {
 66     ch[x][0] = ch[x][1] = 0;siz[x] = cnt[x] = 1;
 67     data[x] = d;fa[x] = pa;
 68 }
 69 inline void Insert(int x) { // 插入
 70     if (Root==0) {
 71         ++tn; Root = tn;newnode(tn,0,x);return;
 72     }
 73     int p = Root,pa = 0;
 74     while (true) {
 75         if (x==data[p]) {
 76             cnt[p]++;pushup(p);pushup(pa);splay(p,0);break;
 77         }
 78         pa = p;
 79         p = ch[p][x > data[p]];
 80         if (p==0) {
 81             p = ++tn;newnode(p,pa,x);
 82             ch[pa][x > data[pa]] = p;
 83             pushup(pa),splay(p,0);break;
 84         }
 85     }
 86 }
 87 inline void Clear(int x) {
 88     ch[x][0] = ch[x][1] = fa[x] = siz[x] = cnt[x] = data[x] = 0;
 89 }
 90 inline void Delete(int x) { // 删除
 91     getrnk(x);
 92     int &p = Root;
 93     if (cnt[p] > 1) {cnt[p]--;pushup(p);return;}
 94     if (!ls && !rs) {Clear(p);p = 0;return;}
 95     if (!ls || !rs) {
 96         int tmp = p;p = ls==0?rs:ls;fa[p] = 0;Clear(tmp);return;
 97     }
 98     int tmp = p,pre = ls; // 找根节点的前一个-左子树的最右边 
 99     while (ch[pre][1]) pre = ch[pre][1];
100     splay(pre,0);
101     rs = ch[tmp][1];fa[ch[tmp][1]] = p;
102     Clear(tmp);
103     pushup(p);
104 }
105 int main() {
106     int n = read();
107     while (n--){
108         int opt = read(),x = read();
109         if (opt==1) Insert(x);
110         else if (opt==2) Delete(x);
111         else if (opt==3) printf("%d
",getrnk(x));
112         else if (opt==4) printf("%d
",getkth(x));
113         else if (opt==5) printf("%d
",getkth(getrnk(x)-1));
114         else printf("%d
",getkth(getrnk(x+1)));
115     }
116     return 0;
117 }

View Code

更新了下板子

  1 #include<cstdio>
  2  
  3 const int N = 100010;
  4 int fa[N],ch[N][2],siz[N],cnt[N],data[N];
  5 int tn,Root;
  6 
  7 inline char nc() {
  8     static char buf[100000],*p1 = buf,*p2 = buf;
  9     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF :*p1++;
 10 }
 11 inline int read() {
 12     int x = 0,f = 1;char ch=nc();
 13     for (; ch<'0'||ch>'9'; ch = nc()) 
 14         if (ch == '-') f = -1;
 15     for (; ch>='0'&&ch<='9'; ch = nc()) 
 16         x = x*10+ch-'0';
 17     return x * f;
 18 }
 19 inline int son(int x) {
 20     return x == ch[fa[x]][1]; // - 
 21 }
 22 inline void pushup(int x) {
 23     siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
 24 }
 25 inline void rotate(int x) {
 26     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 27     if (z) ch[z][c] = x;else Root = x;fa[x] = z; // 调整x的位置
 28     ch[x][!b] = y;fa[y] = x; // 调整y的位置
 29     ch[y][b] = a;if (a) fa[a] = y; // 给y另一个子节点
 30     pushup(y);pushup(x);
 31 }
 32 inline void splay(int x,int rt) {
 33     while (fa[x] != rt) {
 34         int y = fa[x],z = fa[y];
 35         if (z==rt) rotate(x);
 36         else {
 37             if (son(x)==son(y)) rotate(y),rotate(x);
 38             else rotate(x),rotate(x);
 39         }
 40     }
 41 }
 42 inline int getpre(int x) { //得到第一个比x小的数 
 43     int p = Root,ans;
 44     while (p) {
 45         if (x <= data[p]) p = ch[p][0];
 46         else ans = p,p = ch[p][1];
 47     }
 48     return ans;
 49 }
 50 inline int getsuc(int x) { // 得到第一个比x大的数
 51     int p = Root,ans;
 52     while (p) {
 53         if (x >= data[p]) p = ch[p][1];
 54         else ans = p,p = ch[p][0];
 55     }
 56     return ans;
 57 }
 58 inline int getk(int k) { // 得到k的排名
 59     int p = Root,ans = 0;
 60     while (true) {
 61         if (k < data[p]) p = ch[p][0];
 62         else {
 63             ans += (ch[p][0] ? siz[ch[p][0]] : 0);
 64             if (k==data[p]) {
 65                 splay(p,0);return ans+1;
 66             }
 67             ans += cnt[p];
 68             p = ch[p][1];
 69         }
 70     }
 71 }
 72 inline int getkth(int k) { // 得到第k个数
 73     int p = Root;
 74     while (true) {
 75         if (ch[p][0] && k <= siz[ch[p][0]]) p = ch[p][0];
 76         else {
 77             int tmp = (ch[p][0] ? siz[ch[p][0]] : 0) + cnt[p];
 78             if (k <= tmp) return data[p];
 79             k -= tmp; p = ch[p][1];
 80         }
 81     }
 82 }
 83 inline void Insert(int x) { // 插入
 84     if (Root==0) {
 85         ++tn; Root = tn; 
 86         ch[tn][1] = ch[tn][0] = fa[tn] = 0;
 87         siz[tn] = cnt[tn] = 1;data[tn] = x;
 88         return;
 89     }
 90     int p = Root,pa = 0;
 91     while (true) {
 92         if (x==data[p]) {
 93             cnt[p]++;pushup(p);pushup(pa);splay(p,0);break;
 94         }
 95         pa = p;
 96         p = ch[p][x > data[p]];
 97         if (p==0) {
 98             tn++;
 99             ch[tn][1] = ch[tn][0] = 0;siz[tn] = cnt[tn] = 1;
100             fa[tn] = pa;ch[pa][x > data[pa]] = tn;data[tn] = x; //-
101             pushup(pa),splay(tn,0);break;
102         }
103     }
104 }
105 inline void Clear(int x) {
106     ch[x][0] = ch[x][1] = fa[x] = siz[x] = cnt[x] = data[x] = 0;
107 }
108 inline void Delete(int x) { // 删除
109     getk(x);
110     if (cnt[Root] > 1) {cnt[Root]--;pushup(Root);return;}
111     if (!ch[Root][0] && !ch[Root][1]) {Clear(Root);Root = 0;return;}
112     if (!ch[Root][0]) {
113         int tmp = Root;Root = ch[Root][1];fa[Root] = 0;Clear(tmp);return;
114     }
115     else if (!ch[Root][1]) {
116         int tmp = Root;Root = ch[Root][0];fa[Root] = 0;Clear(tmp);return;
117     }
118     int tmp = Root,pre = ch[Root][0];//可以是getpre(data[Root]);等价于下面的while 
119     while (ch[pre][1]) pre = ch[pre][1];
120     splay(pre,0);
121     ch[Root][1] = ch[tmp][1];
122     fa[ch[tmp][1]] = Root;
123     Clear(tmp);
124     pushup(Root);
125 }
126 int main() {
127     int n = read();
128     while (n--){
129         int opt = read(),x = read();
130         if (opt==1) Insert(x);
131         else if (opt==2) Delete(x);
132         else if (opt==3) printf("%d
",getk(x));
133         else if (opt==4) printf("%d
",getkth(x));
134         else if (opt==5) printf("%d
",data[getpre(x)]);
135         else printf("%d
",data[getsuc(x)]);
136     }
137     return 0;
138 }

View Code

另一种写法，放一下吧

  1 #include<cstdio>
  2   
  3 const int N = 100010;
  4 int fa[N],ch[N][2],siz[N],cnt[N],data[N];
  5 int tn,Root;
  6  
  7 inline char nc() {
  8     static char buf[100000],*p1 = buf,*p2 = buf;
  9     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF :*p1++;
 10 }
 11 inline int read() {
 12     int x = 0,f = 1;char ch=nc();
 13     for (; ch<'0'||ch>'9'; ch = nc()) 
 14         if (ch == '-') f = -1;
 15     for (; ch>='0'&&ch<='9'; ch = nc()) 
 16         x = x*10+ch-'0';
 17     return x * f;
 18 }
 19 inline int son(int x) {
 20     return x == ch[fa[x]][1]; // - 
 21 }
 22 inline void pushup(int x) {
 23     siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
 24 }
 25 inline void rotate(int x) {
 26     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 27     if (z) ch[z][c] = x;else Root = x;fa[x] = z; // 调整x的位置
 28     ch[x][!b] = y;fa[y] = x; // 调整y的位置
 29     ch[y][b] = a;if (a) fa[a] = y; // 给y另一个子节点
 30     pushup(y);pushup(x);
 31 }
 32 inline void splay(int x,int rt) {
 33     while (fa[x] != rt) {
 34         int y = fa[x],z = fa[y];
 35         if (z==rt) rotate(x);
 36         else {
 37             if (son(x)==son(y)) rotate(y),rotate(x);
 38             else rotate(x),rotate(x);
 39         }
 40     }
 41 }
 42 inline int getpre(int x) { //得到第一个比x小的数 
 43     int p = ch[Root][0];
 44     while (ch[p][1]) p = ch[p][1];
 45     return p;
 46 }
 47 inline int getsuc(int x) { // 得到第一个比x大的数
 48     int p = ch[Root][1];
 49     while (ch[p][0]) p = ch[p][0];
 50     return p;
 51 }
 52 inline int getk(int k) { // 得到k的排名
 53     int p = Root,ans = 0;
 54     while (true) {
 55         if (k < data[p]) p = ch[p][0];
 56         else {
 57             ans += (ch[p][0] ? siz[ch[p][0]] : 0);
 58             if (k==data[p]) {
 59                 splay(p,0);return ans+1;
 60             }
 61             ans += cnt[p];
 62             p = ch[p][1];
 63         }
 64     }
 65 }
 66 inline int getkth(int k) { // 得到第k个数
 67     int p = Root;
 68     while (true) {
 69         if (ch[p][0] && k <= siz[ch[p][0]]) p = ch[p][0];
 70         else {
 71             int tmp = (ch[p][0] ? siz[ch[p][0]] : 0) + cnt[p];
 72             if (k <= tmp) return data[p];
 73             k -= tmp; p = ch[p][1];
 74         }
 75     }
 76 }
 77 inline void Insert(int x) { // 插入
 78     if (Root==0) {
 79         ++tn; Root = tn; 
 80         ch[tn][1] = ch[tn][0] = fa[tn] = 0;
 81         siz[tn] = cnt[tn] = 1;data[tn] = x;
 82         return;
 83     }
 84     int p = Root,pa = 0;
 85     while (true) {
 86         if (x==data[p]) {
 87             cnt[p]++;pushup(p);pushup(pa);splay(p,0);break;
 88         }
 89         pa = p;
 90         p = ch[p][x > data[p]];
 91         if (p==0) {
 92             tn++;
 93             ch[tn][1] = ch[tn][0] = 0;siz[tn] = cnt[tn] = 1;
 94             fa[tn] = pa;ch[pa][x > data[pa]] = tn;data[tn] = x; //-
 95             pushup(pa),splay(tn,0);break;
 96         }
 97     }
 98 }
 99 inline void Clear(int x) {
100     ch[x][0] = ch[x][1] = fa[x] = siz[x] = cnt[x] = data[x] = 0;
101 }
102 inline void Delete(int x) { // 删除
103     getk(x);
104     if (cnt[Root] > 1) {cnt[Root]--;pushup(Root);return;}
105     if (!ch[Root][0] && !ch[Root][1]) {Clear(Root);Root = 0;return;}
106     if (!ch[Root][0]) {
107         int tmp = Root;Root = ch[Root][1];fa[Root] = 0;Clear(tmp);return;
108     }
109     else if (!ch[Root][1]) {
110         int tmp = Root;Root = ch[Root][0];fa[Root] = 0;Clear(tmp);return;
111     }
112     int tmp = Root,pre = ch[Root][0];//可以是getpre(data[Root]);等价于下面的while 
113     while (ch[pre][1]) pre = ch[pre][1];
114     splay(pre,0);
115     ch[Root][1] = ch[tmp][1];
116     fa[ch[tmp][1]] = Root;
117     Clear(tmp);
118     pushup(Root);
119 }
120 int main() {
121     int n = read();
122     while (n--){
123         int opt = read(),x = read();
124         if (opt==1) Insert(x);
125         else if (opt==2) Delete(x);
126         else if (opt==3) printf("%d
",getk(x));
127         else if (opt==4) printf("%d
",getkth(x));
128         else if (opt==5) Insert(x),printf("%d
",data[getpre(x)]),Delete(x);
129         else Insert(x),printf("%d
",data[getsuc(x)]),Delete(x);
130     }
131     return 0;
132 }

View Code

没有重复数字的情况：

getk和getkth函数

 1 // 只在没有重复数字是使用
 2 inline int getk(int k) {
 3     int p = Root,ans = 0;
 4     while (true) {
 5         if (k == data[p]) {splay(p,0);return ans+1;}
 6         if (k < data[p]) p = ch[p][0];
 7         else {
 8             ans += (ch[p][0] ? siz[ch[p][0]] : 0) + 1;
 9             p = ch[p][1];
10         }
11     }
12 }
13 inline int getkth(int k) {
14     int p = Root;
15     while (true) {
16         if (k == siz[ch[p][0]]+1) return p;
17         if (ch[p][0] && k <= siz[ch[p][0]]) p = ch[p][0];
18         else {
19             k -= ((ch[p][0] ? siz[ch[p][0]] : 0) + 1);
20             p = ch[p][1];
21         }
22     }
23 }

View Code

insert，delete

 1 inline void Insert(int x) {
 2     if (Root==0) {
 3         ++tn;Root = tn;
 4         ch[tn][1] = ch[tn][0] = fa[tn] = 0;
 5         siz[tn] = 1;data[tn] = x;
 6         return ;
 7     }
 8     int p = Root,pa = 0;
 9     while (true) {
10         pa = p;
11         p = ch[p][x > data[p]];
12         if (p==0) {
13             ++tn;
14             ch[tn][1] = ch[tn][0] = 0;fa[tn] = pa;
15             ch[pa][x > data[pa]] = tn;
16             siz[tn] = 1;data[tn] = x;
17             pushup(pa),splay(tn,0);break;
18         }
19     }
20 }
21 inline void Clear(int x) {
22     ch[x][0] = ch[x][1] = fa[x] = siz[x] = data[x] = 0;
23 }
24 inline void Delete(int x) {
25     getk(x);
26     if (!ch[Root][0] && !ch[Root][1]) { Clear(Root);Root = 0;return;}
27     if (!ch[Root][0]) {
28         int tmp = Root;Root = ch[Root][1];fa[Root] = 0;Clear(tmp);return;
29     }
30     else if (!ch[Root][1]) {
31         int tmp = Root;Root = ch[Root][0];fa[Root] = 0;Clear(tmp);return;
32     }
33     int tmp = Root,pre = ch[Root][0];
34     while (ch[pre][1]) pre = ch[pre][1];
35     splay(pre,0);
36     ch[Root][1] = ch[tmp][1];
37     fa[ch[tmp][1]] = Root;
38     Clear(tmp);
39     pushup(Root);
40 }

View Code

查找大于等于x的数或者小于等于：

getpre和getsuc函数

 1 //这两个函数可以等于查找的数
 2 inline int getpre(int x) { // 返回第一个小于等于x的数
 3     int p = Root,ans = 0;
 4     while (p) {
 5         if (x < data[p]) p = ch[p][0];
 6         else ans = p,p = ch[p][1];
 7     }
 8     return ans;
 9 }
10 inline int getsuc(int x) { // 返回第一个大于等于x的数
11     int p = Root,ans = 0;
12     while (p) {
13         if (x > data[p]) p = ch[p][1];
14         else ans = p,p = ch[p][1];
15     }
16 }

View Code

getpre，getsuc函数另一种操作：

getpre(x):找x的前驱，首先找到x的排名k = getk(x)，然后求出排名为k-1的数：pre=getkth(k-1);

getsuc同理