fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 5000000 + 5;
  6.  
  7. int psz;
  8. int key[maxn], pri[maxn];
  9. int ch[maxn][2], siz[maxn];
  10. int ver[maxn];
  11.  
  12. int newnode(int k) {
  13.     int u = ++psz;
  14.     key[u] = k, pri[u] = rand();
  15.     ch[u][0] = ch[u][1] = 0, siz[u] = 1;
  16.     return u;
  17. }
  18.  
  19. void copy(int x, int y) {
  20.     key[x] = key[y], pri[x] = pri[y];
  21.     ch[x][0] = ch[y][0], ch[x][1] = ch[y][1], siz[x] = siz[y];
  22. }
  23.  
  24. void maintain(int u) { siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1; }
  25.  
  26. void split(int u, int k, int &l, int &r) {
  27.     if (u == 0) {
  28.         l = r = 0;
  29.         return;
  30.     }
  31.     int v = ++psz;
  32.     copy(v, u);
  33.     if (k <= key[v]) {
  34.         split(ch[v][0], k, l, ch[v][0]), r = v;
  35.     } else {
  36.         l = v, split(ch[v][1], k, ch[v][1], r);
  37.     }
  38.     maintain(v);
  39. }
  40.  
  41. int merge(int u, int v) {
  42.     if (u == 0 || v == 0)
  43.         return u + v;
  44.     int w = ++psz;
  45.     if (pri[u] > pri[v]) {
  46.         copy(w, u);
  47.         ch[w][1] = merge(ch[w][1], v);
  48.     } else {
  49.         copy(w, v);
  50.         ch[w][0] = merge(u, ch[w][0]);
  51.     }
  52.     maintain(w);
  53.     return w;
  54. }
  55.  
  56. int Insert(int root, int k) {
  57.     int l, r;
  58.     split(root, k, l, r);
  59.     return merge(merge(l, newnode(k)), r);
  60. }
  61.  
  62. int Erase(int root, int k) {
  63.     int l, u, r;
  64.     split(root, k, l, r);
  65.     split(r, k + 1, u, r);
  66.     return merge(merge(l, merge(ch[u][0], ch[u][1])), r);
  67. }
  68.  
  69. int Rank(int root, int k) {
  70.     int u = root, ret = 0;
  71.     while (u) {
  72.         if (key[u] < k)
  73.             ret += siz[ch[u][0]] + 1, u = ch[u][1];
  74.         else
  75.             u = ch[u][0];
  76.     }
  77.     return ret + 1;
  78. }
  79.  
  80. int Select(int root, int k) {
  81.     int u = root;
  82.     while (u) {
  83.         if (siz[ch[u][0]] == k - 1)
  84.             break;
  85.         if (k <= siz[ch[u][0]])
  86.             u = ch[u][0];
  87.         else
  88.             k -= siz[ch[u][0]] + 1, u = ch[u][1];
  89.     }
  90.     return key[u];
  91. }
  92.  
  93. int main() {
  94.     int n, root = 0;
  95.     cin >> n;
  96.     ver[0] = root;
  97.     for (int i = 1; i <= n; i++) {
  98.         int v, op, x;
  99.         cin >> v >> op >> x;
  100.         if (op == 1)
  101.             ver[i] = Insert(ver[v], x);
  102.         else if (op == 2)
  103.             ver[i] = Erase(ver[v], x);
  104.         else if (op == 3) {
  105.             cout << Rank(ver[v], x) << '\n';
  106.             ver[i] = ver[v];
  107.         } else if (op == 4) {
  108.             cout << Select(ver[v], x) << '\n';
  109.             ver[i] = ver[v];
  110.         } else if (op == 5) {
  111.             cout << Select(ver[v], Rank(ver[v], x) - 1) << '\n';
  112.             ver[i] = ver[v];
  113.         } else if (op == 6) {
  114.             cout << Select(ver[v], Rank(ver[v], x + 1)) << '\n';
  115.             ver[i] = ver[v];
  116.         }
  117.     }
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/RJpNNW
language:
C++ (gcc 8.3)
created:
285 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!