普通平衡树：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <time.h>
#include <random>
#define int long long
#define N 100005
#define M 25
using namespace std;
mt19937_64 rd(time(0));
struct fhq_treap{int cnt = 0,rt;struct node{int lson,rson,val,k,sz;}tr[N * M];#define ls(x) tr[x].lson#define rs(x) tr[x].rsonint build(int val) {tr[++cnt].val = val,tr[cnt].lson = tr[cnt].rson = 0;tr[cnt].sz = 1,tr[cnt].k = rd();return cnt;}void pushup(int x) {tr[x].sz = tr[ls(x)].sz + tr[rs(x)].sz + 1;}void split(int cur,int x,int &a,int &b) {if (cur == 0) return a = b = 0,void();if (tr[cur].val <= x) a = cur,split(rs(cur),x,rs(cur),b);else b = cur,split(ls(cur),x,a,ls(cur));pushup(cur);}void split_sz(int cur,int x,int &a,int &b) {if (cur == 0) return a = b = 0,void();if (tr[ls(cur)].sz + 1 <= x) a = cur,split_sz(rs(cur),x - tr[ls(cur)].sz - 1,rs(cur),b);else b = cur,split_sz(ls(cur),x,a,ls(cur));pushup(cur);}int merge(int a,int b) {if (!a || !b) return a + b;if (tr[a].k < tr[b].k) return tr[a].rson = merge(tr[a].rson,b),pushup(a),a;else return tr[b].lson = merge(a,tr[b].lson),pushup(b),b;}void insert(int val) {int x,y;split(rt,val,x,y);rt = merge(merge(x,build(val)),y);}void del(int val) {int x,y,z;split(rt,val,x,y);split(x,val - 1,x,z);rt = merge(merge(x,merge(tr[z].lson,tr[z].rson)),y);}int find(int val) {int x,y;split(rt,val - 1,x,y);int ans = tr[x].sz + 1;rt = merge(x,y);return ans;}int querykth(int k) {int x,y,z;split_sz(rt,k - 1,x,y);split_sz(y,1,z,y);int ans = tr[z].val;rt = merge(merge(x,z),y);return ans;}int find_before(int val) {int x,y,z;split(rt,val - 1,x,y);// split_sz(x,tr[x].sz,x,z);int p = x;while(tr[p].rson) p = tr[p].rson;int ans = tr[p].val;// rt = merge(merge(x,z),y);rt = merge(x,y);return ans;}int find_after(int val) {int x,y,z;split(rt,val,x,y);int p = y;// split_sz(y,1,z,y);while(tr[p].lson) p = tr[p].lson;int ans = tr[p].val;rt = merge(x,y);// rt = merge(merge(x,z),y);return ans;}
}t;
// fhq_treap::node t=1;
int T;
signed main(){cin >> T;for (int op,x,lstans = 0;T --;) {scanf("%lld%lld",&op,&x);if (op == 1) t.insert(x);else if (op == 2) t.del(x);else if (op == 3) lstans = t.find(x);else if (op == 4) lstans = t.querykth(x);else if (op == 5) lstans = t.find_before(x);else lstans = t.find_after(x);if (op != 1 && op != 2) printf("%lld\n",lstans);}return 0;
}
文艺平衡树：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <random>
#include <time.h>
#define int long long
#define N 100005
using namespace std;
int n,m;
mt19937_64 rd(time(0));
struct fhq_treap{int cnt = 0,rt;struct node{int lson,rson,val,k,sz;}tr[N * 25];int lz[N * 25];#define ls(x) tr[x].lson#define rs(x) tr[x].rsonint build(int val) {tr[++cnt].val = val,tr[cnt].lson = tr[cnt].rson = 0,tr[cnt].sz = 1,tr[cnt].k = rd();return cnt;}void pushup(int x) {tr[x].sz = tr[ls(x)].sz + tr[rs(x)].sz + 1;}void pushdown(int x) {swap(tr[x].lson,tr[x].rson);lz[x] = 0,lz[ls(x)] ^= 1,lz[rs(x)] ^= 1;}void split(int cur,int x,int &a,int &b) {if (cur == 0) return a = b = 0,void();if (lz[cur]) pushdown(cur);if (tr[ls(cur)].sz + 1 <= x) a = cur,split(rs(cur),x - tr[ls(cur)].sz - 1,rs(cur),b);else b = cur,split(ls(cur),x,a,ls(cur));pushup(cur);}int merge(int a,int b) {if (!a || !b) return a + b;if (tr[a].k < tr[b].k) {if (lz[a]) pushdown(a);tr[a].rson = merge(tr[a].rson,b),pushup(a);return a;}else {if (lz[b]) pushdown(b);tr[b].lson = merge(a,tr[b].lson),pushup(b);return b;}}void insert(int val) {int x,y;split(rt,val,x,y);rt = merge(merge(x,build(val)),y);}void debug(int cur) {if (cur == 0) return ;printf("%lld %lld %lld %lld\n",cur,tr[cur].lson,tr[cur].rson,lz[cur]);debug(tr[cur].lson),debug(tr[cur].rson);}void getans(int cur) {if (cur == 0) return;if (lz[cur]) pushdown(cur);getans(ls(cur));printf("%lld ",tr[cur].val);getans(rs(cur));}
}t;
signed main(){cin >> n >> m;for (int i = 1;i <= n;i ++) t.insert(i);for (int l,r;m --;) {scanf("%lld%lld",&l,&r);int x,y,z;t.split(t.rt,r,x,y);t.split(x,l - 1,x,z);t.lz[z] ^= 1;t.rt = t.merge(t.merge(x,z),y);// t.debug(t.rt);}t.getans(t.rt);return 0;
}