无旋Treap【模板】P3369

  1 #include<cstdio>
  2 #include<iostream>
  3 #define outd(x) printf("%dn",x)
  4 #define outld(x) printf("%lldn",x)
  5 #define ls(x)  arr[x].child[0]
  6 #define rs(x)  arr[x].child[1]
  7 inline int read_int()
  8 {
  9     char c;
 10     int ret = 0,sgn = 1;
 11     do { c = getchar(); } while ((c < ‘0‘ || c > ‘9‘) && c != ‘-‘);
 12     if (c == ‘-‘)  sgn = -1;  else ret = c - ‘0‘;
 13     while ((c = getchar()) >= ‘0‘ && c <= ‘9‘)  ret = ret * 10 + (c - ‘0‘);
 14     return sgn * ret;
 15 }
 16 using namespace std;
 17 
 18 const int maxn = 100000 + 10;
 19 
 20 struct node
 21 {
 22     int child[2],size,value,key;
 23 }arr[maxn];
 24 int tot;     //当前节点个数
 25 
 26 
 27 
 28 inline void push_up(int index)
 29 {
 30     arr[index].size = arr[ls(index)].size + arr[rs(index)].size + 1;
 31 }
 32 
 33 void split(int root,int& x,int& y,int value)  //x中的小于或等于value，y中的大于value
 34 {
 35     if (!root) { x = y = 0; return; }
 36     if (arr[root].value <= value) { x = root; split(rs(root),rs(x),y,value); }
 37     else { y = root; split(ls(root),x,ls(y),value); }
 38     push_up(root);
 39 }
 40 
 41 void merge(int&root,int x,int y)
 42 {
 43     if (!x || !y) { root = x + y; return; }     //其中一个为0，root等于另一个
 44     if (arr[x].key < arr[y].key) { root = x; merge(rs(root),y); }
 45     else { root = y; merge(ls(root),ls(y)); }
 46     push_up(root);
 47 }
 48 
 49 inline void insert(int& root,int value)
 50 {
 51     int x = 0,y = 0,z = ++tot;
 52     arr[z].value = value,arr[z].size = 1,arr[z].key = rand();
 53     split(root,value);
 54     merge(x,z);
 55     merge(root,y);
 56 }
 57 
 58 inline void erase(int& root,int value)
 59 {
 60     int x = 0,z = 0;
 61     split(root,value);
 62     split(x,z,value - 1);        //z中全是value
 63     merge(z,ls(z),rs(z));
 64     merge(x,z);
 65     merge(root,y);
 66 }
 67 
 68 inline int Kth_number(int root,int k) 
 69 {
 70     while (arr[ls(root)].size + 1 != k)
 71     {
 72         if (arr[ls(root)].size >= k)  root = ls(root);
 73         else { k -= (arr[ls(root)].size + 1); root = rs(root); }
 74     }
 75     return arr[root].value;
 76 }
 77 
 78 inline int Get_rank(int& root,int value)
 79 {
 80     int x = 0,y = 0;
 81     split(root,value - 1);
 82     int res = arr[x].size + 1;
 83     merge(root,y);
 84     return res;
 85 }
 86 
 87 inline int Pre(int& root,int value)
 88 {
 89     int x = 0,y = 0;
 90     split(root,value - 1);
 91     int res = Kth_number(x,arr[x].size);
 92     merge(root,y);    //merge回去
 93     return res;
 94 }
 95 
 96 inline int Suf(int& root,int value)
 97 {
 98     int x = 0,y = 0;
 99     split(root,value);
100     int res = Kth_number(y,1);
101     merge(root,y);
102     return res;
103 }
104 
105 int n,op,root;
106 
107 int main()
108 {
109     srand(19260817);
110     n = read_int();
111     while (n--)
112     {
113         op = read_int();
114         if (op == 1)  insert(root,read_int());
115         if (op == 2)  erase(root,read_int());
116         if (op == 3)  outd(Get_rank(root,read_int()));
117         if (op == 4)  outd(Kth_number(root,read_int()));
118         if (op == 5)  outd(Pre(root,read_int()));
119         if (op == 6)  outd(Suf(root,read_int()));
120     }
121 
122     return 0;
123 }