Treap 模板

#include <ctime>
#include <iostream>
#include <random>

using namespace std;

signed gen() {
   static mt19937 mt(time(0));
   static int cnt = 0;
   cnt++;
   if (cnt == 1e5) {
      cnt = 0;
      mt.seed(time(0));
   }
   return mt();
}

struct Treap {
  public:
   Treap() { root = NULL; }
   ~Treap() { clear(root); }
   void insert(int val) { root = insert(root, val); }
   void erase(int val) { root = erase(root, val); }
   int querry_rank(int val) { return querry_rank(root, val); }
   int querry_val(int rank) { return querry_val(root, rank); }
   int querry_less(int val) { return querry_less(root, val); }
   int querry_more(int val) { return querry_more(root, val); }

  private:
   struct Node {
      int val, pri, cnt, size;
      Node *son[2];
      Node(int x) {
         val = x;
         cnt = 1;
         size = 1;
         pri = gen();
         son[0] = son[1] = NULL;
      }

      void upd_size() {
         size = cnt + count_size(son[0]) + count_size(son[1]);
      }

      int count_size(Node *t) {
         if (t == NULL) return 0;
         return t->size;
      }
   };

   Node *root;

   Node *_rotate(Node *parent, Node *son) {
      auto get_d = [&]() -> int {
         if (parent->son[0] == son)
            return 0;
         else
            return 1;
      };

      int d = get_d();  // 0 - left, 1 - right

      parent->son[d] = son->son[d ^ 1];
      son->son[d ^ 1] = parent;
      parent->upd_size();
      son->upd_size();
      return son;
   }

   Node *insert(Node *p, int val) {
      if (p == NULL) return new Node(val);
      if (p->val > val) {
         p->son[0] = insert(p->son[0], val);
         p->upd_size();
         if (p->son[0]->pri > p->pri) p = _rotate(p, p->son[0]);
      } else if (p->val < val) {
         p->son[1] = insert(p->son[1], val);
         p->upd_size();
         if (p->son[1]->pri > p->pri) p = _rotate(p, p->son[1]);
      } else {
         p->cnt++;
         p->upd_size();
      }
      return p;
   }

   Node *erase(Node *p, int val) {
      if (p == NULL) return NULL;
      if (p->val > val) {
         p->son[0] = erase(p->son[0], val);
         p->upd_size();
      } else if (p->val < val) {
         p->son[1] = erase(p->son[1], val);
         p->upd_size();
      } else {
         if (p->cnt == 1) {
            if (p->son[0] == NULL && p->son[1] == NULL) {
               delete p;
               return NULL;
            } else if (p->son[1] == NULL) {
               auto t = p->son[0];
               delete p;
               return t;
            } else if (p->son[0] == NULL) {
               auto t = p->son[1];
               delete p;
               return t;
            } else {
               if (p->son[0]->pri > p->son[1]->pri) {
                  p = _rotate(p, p->son[0]);
                  p->son[1] = erase(p->son[1], val);
               } else {
                  p = _rotate(p, p->son[1]);
                  p->son[0] = erase(p->son[0], val);
               }
               p->upd_size();
               return p;
            }
         } else {
            p->cnt--;
            p->upd_size();
         }
      }

      return p;
   }

   int querry_rank(Node *p, int val) {
      if (p == NULL) return 0;
      if (p->val > val)
         return querry_rank(p->son[0], val);
      else if (p->val < val)
         return p->size - p->count_size(p->son[1]) +
                querry_rank(p->son[1], val);
      return p->count_size(p->son[0]);
   }

   int querry_val(Node *p, int rank) {
      if (p == NULL) return -1e9;
      if (p->count_size(p->son[0]) >= rank) {
         return querry_val(p->son[0], rank);
      } else if (p->size - p->count_size(p->son[1]) < rank) {
         return querry_val(p->son[1],
                           rank - p->size + p->count_size(p->son[1]));
      } else {
         return p->val;
      }
   }

   int querry_less(Node *p, int val) {
      if (p == NULL) return -1e9;
      if (p->val >= val) return querry_less(p->son[0], val);
      if (p->val < val)
         return max(p->val, querry_less(p->son[1], val));
      return -1e9;
   }

   int querry_more(Node *p, int val) {
      if (p == NULL) return 1e9;
      if (p->val <= val) return querry_more(p->son[1], val);
      if (p->val > val)
         return min(p->val, querry_more(p->son[0], val));
      return 0;
   }

   void clear(Node *p) {
      if (p == NULL) return;
      clear(p->son[0]);
      clear(p->son[1]);
      delete p;
   }
};

int main() {
   cin.tie(0)->sync_with_stdio(false);

   int t;
   cin >> t;

   Treap tp;

   while (t--) {
      int op, x;
      cin >> op >> x;

      if (op == 1) {
         tp.insert(x);
      } else if (op == 2) {
         tp.erase(x);
      } else if (op == 3) {
         cout << tp.querry_rank(x) + 1 << '\n';
      } else if (op == 4) {
         cout << tp.querry_val(x) << '\n';
      } else if (op == 5) {
         cout << tp.querry_less(x) << '\n';
      } else if (op == 6) {
         cout << tp.querry_more(x) << '\n';
      }
   }

   return 0;
}

/// @! 一定要注意，空的情况，在维护父节点的时候，必须要置空。
#include <iostream>
#include <random>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

signed gen() {
   static mt19937 rng(time(0));
   static int cnt = 0;
   cnt++;
   if (cnt == N / 10) {
      cnt = 0;
      rng.seed(time(0) ^ rng());
   }
   return rng();
}

struct Node {
   int son[2], p;
   int sz, cnt;
   int val, pri;

   void init(int v, int par) {
      val = v, p = par;
      sz = 1;
      cnt = 1;
      son[0] = son[1] = 0;
      pri = gen();
   }
} Tree[N];

int root = 0;

void update_size(int p) {
   Tree[p].sz = Tree[p].cnt;
   if (Tree[p].son[0]) Tree[p].sz += Tree[Tree[p].son[0]].sz;
   if (Tree[p].son[1]) Tree[p].sz += Tree[Tree[p].son[1]].sz;
}

void _rotate(int x) {
   int y = Tree[x].p;
   int z = Tree[y].p;

   int d = Tree[y].son[1] == x;

   Tree[y].son[d] = Tree[x].son[d ^ 1];
   Tree[x].son[d ^ 1] = y;

   Tree[x].p = z;
   Tree[y].p = x;

   if (Tree[y].son[d]) Tree[Tree[y].son[d]].p = y;

   update_size(y);
   update_size(x);

   if (z == 0)
      root = x;
   else
      Tree[z].son[Tree[z].son[1] == y] = x;
}

int id = 0;

void insert(int v) {
   // cerr << "insert " << v << endl;
   int now = root, pre = 0;

   while (now && Tree[now].val != v) {
      pre = now;
      now = Tree[pre].son[v > Tree[pre].val];
   }

   if (now) {
      Tree[now].cnt++;
      update_size(now);
   } else {
      now = ++id;
      Tree[now].init(v, pre);
      if (pre) Tree[pre].son[v > Tree[pre].val] = now;
   }

   while (pre && Tree[pre].pri < Tree[now].pri) {
      update_size(pre);
      _rotate(now);
      pre = Tree[now].p;
   }

   while (now) {
      root = now;
      update_size(now);
      now = Tree[now].p;
   }
}

void erase(int v) {
   // cerr << "IN erase " << v << endl;
   int now = root, pre = 0;

   while (now && Tree[now].val != v) {
      pre = now;
      now = Tree[pre].son[v > Tree[pre].val];
   }

   if (now == 0) return;

   Tree[now].cnt--;
   update_size(now);

   if (Tree[now].cnt == 0) {
      while (Tree[now].son[0] != 0 && Tree[now].son[1] != 0) {
         _rotate(Tree[now].son[Tree[Tree[now].son[0]].pri <
                               Tree[Tree[now].son[1]].pri]);
         pre = Tree[now].p;
      }
      if (pre) {
         Tree[pre].son[Tree[pre].son[1] == now] =
             Tree[now].son[0] + Tree[now].son[1];
         if (Tree[now].son[0] + Tree[now].son[1])
            Tree[Tree[now].son[0] + Tree[now].son[1]].p = pre;
         now = pre;
      } else {
         root = Tree[now].son[0] + Tree[now].son[1];
         if (root) Tree[root].p = 0;
         now = 0;
      }
   }

   while (now) {
      root = now;
      update_size(now);
      now = Tree[now].p;
   }
}

int querry_val(int rk) {
   // cerr << "IN query_val" << endl;
   int now = root;

   while (rk) {
      // cerr << "rk = " << rk << endl;
      int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
      if (Lsize >= rk) {
         now = Tree[now].son[0];
      } else if (Lsize + Tree[now].cnt >= rk) {
         return Tree[now].val;
      } else {
         rk -= Lsize + Tree[now].cnt;
         now = Tree[now].son[1];
      }
   }
   return 0;
}

int query_rank(int x) {
   int now = root;
   int tot = 0;

   while (now && Tree[now].val != x) {
      int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
      if (Tree[now].val > x) {
         now = Tree[now].son[0];
      } else {
         tot += Lsize + Tree[now].cnt;
         now = Tree[now].son[1];
      }
   }

   if (now && Tree[now].son[0]) tot += Tree[Tree[now].son[0]].sz;

   return tot + 1;
}

int nxt(int cur, int x) {
   // cerr << "IN nxt " << cur << " " << x << endl;
   if (cur == 0) return 1e9;
   if (Tree[cur].val <= x) return nxt(Tree[cur].son[1], x);
   return min(nxt(Tree[cur].son[0], x), Tree[cur].val);
}

int pre(int cur, int x) {
   // cerr << "IN pre " << cur << " " << x << endl;
   if (cur == 0) return -1e9;
   if (Tree[cur].val >= x) return pre(Tree[cur].son[0], x);
   return max(pre(Tree[cur].son[1], x), Tree[cur].val);
}

int main() {
   cin.tie(0)->sync_with_stdio(false);
   int t;
   cin >> t;
   while (t--) {
      int op, x;
      cin >> op >> x;
      if (op == 1) insert(x);
      if (op == 2) erase(x);
      if (op == 3) cout << query_rank(x) << '\n';
      if (op == 4) cout << querry_val(x) << '\n';
      if (op == 5) cout << pre(root, x) << '\n';
      if (op == 6) cout << nxt(root, x) << '\n';
   }
   return 0;
}

#include <iostream>
#include <random>
#include <tuple>

using namespace std;

unsigned gen() {
   static mt19937 rng(time(nullptr));
   static int cnt = 0;
   cnt++;
   if (cnt == 19937) {
      rng.seed(time(nullptr));
      cnt = 0;
   }
   return rng();
}

struct Treap {
   struct Node {
      int val, cnt, pri, size;
      Node* son[2];

      Node(int v) : val(v) {
         pri = gen();
         cnt = 1;
         size = 1;
         son[0] = son[1] = nullptr;
      }

      void upd_size() {
         size = cnt;
         if (son[0]) size += son[0]->size;
         if (son[1]) size += son[1]->size;
      }

      int count_size(Node* p) {
         if (p == nullptr) return 0;
         return p->size;
      }
   };

   Node* root;
   Treap() : root(nullptr) {}
   ~Treap() { clear(root); }

   tuple<Node*, Node*, Node*> split_val(Node* p, int val) {
      if (p == nullptr) return {nullptr, nullptr, nullptr};
      if (p->val < val) {
         auto [l, m, r] = split_val(p->son[1], val);
         p->son[1] = l;
         p->upd_size();
         return {p, m, r};
      } else if (p->val == val) {
         Node *l = p->son[0], *r = p->son[1];
         p->son[0] = p->son[1] = nullptr;
         p->upd_size();
         return {l, p, r};
      } else {
         auto [l, m, r] = split_val(p->son[0], val);
         p->son[0] = r;
         p->upd_size();
         return {l, m, p};
      }

      return {nullptr, nullptr, nullptr};
   }

   Node* merge(Node* l, Node* r) {
      if (l == nullptr) return r;
      if (r == nullptr) return l;

      if (l->pri > r->pri) {
         l->son[1] = merge(l->son[1], r);
         l->upd_size();
         return l;
      } else {
         r->son[0] = merge(l, r->son[0]);
         r->upd_size();
         return r;
      }
      return nullptr;
   }

   void insert(int v) {
      auto [l, m, r] = split_val(root, v);
      if (m == nullptr) {
         m = new Node(v);
      } else {
         m->cnt++;
         m->upd_size();
      }
      root = merge(l, merge(m, r));
   }

   void erase(int v) {
      auto [l, m, r] = split_val(root, v);
      if (m != nullptr) {
         m->cnt--;
         if (m->cnt == 0) {
            delete m;
            m = nullptr;
         } else m -> upd_size();
      }
      root = merge(l, merge(m, r));
   }

   int querry_rank(int val) { return querry_rank(root, val); }
   int querry_rank(Node* p, int val) {
      if (p == NULL) return 0;
      if (p->val > val)
         return querry_rank(p->son[0], val);
      else if (p->val < val)
         return p->size - p->count_size(p->son[1]) +
                querry_rank(p->son[1], val);
      return p->count_size(p->son[0]);
   }

   int querry_val(int rk) { return querry_val(root, rk); }
   int querry_val(Node* p, int rank) {
      if (p == NULL) return -1e9;
      if (p->count_size(p->son[0]) >= rank) {
         return querry_val(p->son[0], rank);
      } else if (p->size - p->count_size(p->son[1]) < rank) {
         return querry_val(p->son[1],
                           rank - p->size + p->count_size(p->son[1]));
      } else {
         return p->val;
      }
   }

   int querry_less(int val) { return querry_less(root, val); }
   int querry_less(Node* p, int val) {
      if (p == NULL) return -1e9;
      if (p->val >= val) return querry_less(p->son[0], val);
      if (p->val < val)
         return max(p->val, querry_less(p->son[1], val));
      return -1e9;
   }

   int querry_more(int val) { return querry_more(root, val); }
   int querry_more(Node* p, int val) {
      if (p == NULL) return 1e9;
      if (p->val <= val) return querry_more(p->son[1], val);
      if (p->val > val)
         return min(p->val, querry_more(p->son[0], val));
      return 0;
   }

   void clear(Node* p) {
      if (p == NULL) return;
      clear(p->son[0]);
      clear(p->son[1]);
      delete p;
   }
};

int main() {
   cin.tie(0)->sync_with_stdio(false);

   int t;
   cin >> t;

   Treap tp;

   while (t--) {
      int op, x;
      cin >> op >> x;

      if (op == 1) {
         tp.insert(x);
      } else if (op == 2) {
         tp.erase(x);
      } else if (op == 3) {
         cout << tp.querry_rank(x) + 1 << '\n';
      } else if (op == 4) {
         cout << tp.querry_val(x) << '\n';
      } else if (op == 5) {
         cout << tp.querry_less(x) << '\n';
      } else if (op == 6) {
         cout << tp.querry_more(x) << '\n';
      }
   }

   return 0;
}

#include <iostream>
#include <random>
#include <tuple>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

signed gen() {
   static mt19937 rng(time(0));
   static int cnt = 0;
   cnt++;
   if (cnt == N / 10) {
      cnt = 0;
      rng.seed(time(0) ^ rng());
   }
   return rng();
}

struct Node {
   int son[2];
   int sz, cnt;
   int val, pri;

   void init(int v) {
      val = v;
      sz = 1;
      cnt = 1;
      son[0] = son[1] = 0;
      pri = gen();
   }
} Tree[N];

int root = 0;

// FHQ-Treap

void update_size(int p) {
   Tree[p].sz = Tree[p].cnt;
   if (Tree[p].son[0]) Tree[p].sz += Tree[Tree[p].son[0]].sz;
   if (Tree[p].son[1]) Tree[p].sz += Tree[Tree[p].son[1]].sz;
}

int id = 0;

pair<int, int> split(int cur, int v) {
   // 分裂成 [-inf , v] 和 [v + 1 , inf]
   if (cur == 0) return {0, 0};
   if (Tree[cur].val > v) {
      auto [l, r] = split(Tree[cur].son[0], v);
      Tree[cur].son[0] = r;
      update_size(cur);
      return {l, cur};
   } else {
      auto [l, r] = split(Tree[cur].son[1], v);
      Tree[cur].son[1] = l;
      update_size(cur);
      return {cur, r};
   }
   return {0, 0};
}

int merge(int l, int r) {
   // 合并两个子树
   if (l == 0 || r == 0) return l + r;
   if (Tree[l].pri > Tree[r].pri) {
      Tree[l].son[1] = merge(Tree[l].son[1], r);
      update_size(l);
      return l;
   } else {
      Tree[r].son[0] = merge(l, Tree[r].son[0]);
      update_size(r);
      return r;
   }
   return 0;
}

void insert(int v) {
   auto [t, r] = split(root, v); // [-inf , v] , [v + 1 , inf]
   auto [l, m] = split(t, v - 1);// [-inf , v - 1] , [v , v]
   if (m == 0) {
      m = ++id;
      Tree[m].init(v);
   } else {
      Tree[m].cnt++;
      Tree[m].sz++;
   }

   root = merge(merge(l, m), r);
}

void erase(int v) {
   auto [t, r] = split(root, v); // [-inf , v] , [v + 1 , inf]
   auto [l, m] = split(t, v - 1);// [-inf , v - 1] , [v , v]
   if (m != 0) {
      Tree[m].cnt--;
      Tree[m].sz--;
      if (Tree[m].cnt == 0) m = 0;
   }

   root = merge(l, merge(m, r));
}

int querry_val(int rk) {
   int now = root;

   while (rk) {
      int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
      if (Lsize >= rk) {
         now = Tree[now].son[0];
      } else if (Lsize + Tree[now].cnt >= rk) {
         return Tree[now].val;
      } else {
         rk -= Lsize + Tree[now].cnt;
         now = Tree[now].son[1];
      }
   }
   return 0;
}

int query_rank(int x) {
   int now = root;
   int tot = 0;

   while (now && Tree[now].val != x) {
      int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
      if (Tree[now].val > x) {
         now = Tree[now].son[0];
      } else {
         tot += Lsize + Tree[now].cnt;
         now = Tree[now].son[1];
      }
   }

   if (now && Tree[now].son[0]) tot += Tree[Tree[now].son[0]].sz;

   return tot + 1;
}

int nxt(int cur, int x) {
   if (cur == 0) return 1e9;
   if (Tree[cur].val <= x) return nxt(Tree[cur].son[1], x);
   return min(nxt(Tree[cur].son[0], x), Tree[cur].val);
}

int pre(int cur, int x) {
   if (cur == 0) return -1e9;
   if (Tree[cur].val >= x) return pre(Tree[cur].son[0], x);
   return max(pre(Tree[cur].son[1], x), Tree[cur].val);
}

int main() {
   cin.tie(0)->sync_with_stdio(false);
   int t;
   cin >> t;
   while (t--) {
      int op, x;
      cin >> op >> x;
      if (op == 1) insert(x);
      if (op == 2) erase(x);
      if (op == 3) cout << query_rank(x) << '\n';
      if (op == 4) cout << querry_val(x) << '\n';
      if (op == 5) cout << pre(root, x) << '\n';
      if (op == 6) cout << nxt(root, x) << '\n';
   }
   return 0;
}

#include <iostream>
#include <random>
#include <tuple>

using namespace std;

unsigned gen() {
   static mt19937 rng(time(nullptr));
   static int cnt = 0;
   cnt++;
   if (cnt == 100000) {
      rng.seed(time(nullptr));
      cnt = 0;
   }
   return rng();
}

struct Treap {
   struct Node {
      int val, pri, size, cnt;
      Node* son[2];
      int lz;
      Node(int v) : val(v) {
         size = 1;
         cnt = 1;
         pri = gen();
         son[0] = son[1] = nullptr;
         lz = 0;
      };

      void upd_size() {
         size = cnt;
         if (son[0]) size += son[0]->size;
         if (son[1]) size += son[1]->size;
      }

      void push_down() {
         if (lz) {
            swap(son[0], son[1]);
            if (son[0]) son[0]->lz ^= lz;
            if (son[1]) son[1]->lz ^= lz;
            lz = 0;
         }
      }
   };

   Node* root;

   Treap() : root(nullptr) {}

   pair<Node*, Node*> split_size(Node* p, int sz) {
      if (p == nullptr) return {nullptr, nullptr};

      p->push_down();

      int l_size = p->son[0] ? p->son[0]->size : 0;
      if (l_size >= sz) {
         auto [l, r] = split_size(p->son[0], sz);
         p->son[0] = r;
         p->upd_size();
         return {l, p};
      } else {
         auto [l, r] = split_size(p->son[1], sz - l_size - 1);
         p->son[1] = l;
         p->upd_size();
         return {p, r};
      }
      return {nullptr, nullptr};
   }

   Node* merge(Node* l, Node* r) {
      if (l == nullptr && r == nullptr) return nullptr;
      if (l == nullptr) return r;
      if (r == nullptr) return l;
      l->push_down(), r->push_down();

      if (l->pri > r->pri) {
         l->son[1] = merge(l->son[1], r);
         l->upd_size();
         return l;
      } else {
         r->son[0] = merge(l, r->son[0]);
         r->upd_size();
         return r;
      }
      return nullptr;
   }

   void insert(int v) {
      auto [l, t] = split_size(root, v);
      auto [m, r] = split_size(t, v + 1);
      if (m == nullptr)
         m = new Node(v);
      else
         m->cnt++, m->upd_size();
      root = merge(merge(l, m), r);
   }

   void erase(int v) {
      auto [l, t] = split_size(root, v);
      auto [m, r] = split_size(t, v + 1);
      if (m != nullptr) {
         m->cnt--;
         if (m->cnt == 0) delete m, m = nullptr;
         else m -> upd_size();
      }
      root = merge(merge(l, m), r);
   }

   void reverse(int lv, int rv) {
      auto [l, t] = split_size(root, lv - 1);
      auto [m, r] = split_size(t, rv - lv + 1);
      if (m != nullptr) m->lz ^= 1;
      root = merge(merge(l, m), r);
   }

   void print(Node* p) {
      if (p == nullptr) return;
      p->push_down();
      print(p->son[0]);
      cout << p->val << " ";
      print(p->son[1]);
   }

   void print() { print(root); }
};

int main() {
   int n, m;
   cin >> n >> m;

   Treap tp;

   for (int i = 1; i <= n; i++) tp.insert(i);

   while (m--) {
      int l, r;
      cin >> l >> r;
      tp.reverse(l, r);
      // for (int i = 1; i <= n; i++) cout << i << ' ';
      // cout << '\n';
      // for (int i = 1; i <= n; i++) cout << '|' << ' ';
      // cout << '\n';
      // for (int i = 1; i <= n; i++) cout << 'v' << ' ';
      // cout << '\n';

      // tp.print();
      // cout << '\n';
      // cout << '\n';
   }

   tp.print();

   return 0;
}