Treap + FHQ Treap_综合

一：Treap

支持：插入、删除、查询 $x$ 的排名、查询排名为 $x$ 的数、查前驱、查后继、左旋右旋
模板题：P3369 【模板】普通平衡树

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int INF = 1e9 + 7;
const int maxn = 1e5 + 5;
int rt, tot;
int sz[maxn], val[maxn], cnt[maxn];
int rd[maxn], son[maxn][2];inline void pushup(int x) {sz[x] = sz[son[x][0]] + sz[son[x][1]] + cnt[x];
}
inline void rotate(int &x, int y) {int ii = son[x][y^1];son[x][y^1] = son[ii][y], son[ii][y] = x;pushup(x), pushup(ii), x = ii;
}
void ins(int &p, int x) {if(!p) {p = ++tot, sz[p] = cnt[p] = 1;val[p] = x, rd[p] = rand();return;}if(val[p] == x) return cnt[p]++, sz[p]++, void();int d = x > val[p]; ins(son[p][d], x);if(rd[p] < rd[son[p][d]]) rotate(p, d^1);pushup(p);
}
void del(int &p, int x) {if(!p) return;if(x != val[p]) del(son[p][x>val[p]], x);else {if(!son[p][0] && !son[p][1]) {cnt[p]--, sz[p]--;if(cnt[p] == 0) p = 0;} else if(son[p][0] && !son[p][1]) {rotate(p, 1), del(son[p][1], x);} else if(!son[p][0] && son[p][1]) {rotate(p, 0), del(son[p][0], x);} else {int d = rd[son[p][0]] > rd[son[p][1]];rotate(p, d), del(son[p][d], x);}}pushup(p);
}
int get_rank(int p, int x) {if(!p) return 0;if(val[p] == x) return sz[son[p][0]] + 1;if(val[p] < x) return sz[son[p][0]] + cnt[p] + get_rank(son[p][1], x);return get_rank(son[p][0], x);	// val[p]>x
}
int kth(int p, int x) {if(!p) return 0;if(sz[son[p][0]] >= x) return kth(son[p][0], x);else if(sz[son[p][0]] + cnt[p] < x) return kth(son[p][1], x-cnt[p]-sz[son[p][0]]);else return val[p];
}
int pre(int p, int x) {if(!p) return -INF;if(val[p] >= x) return pre(son[p][0], x);else return max(val[p], pre(son[p][1], x));
}
int suf(int p, int x) {if(!p) return INF;if(val[p] <= x) return suf(son[p][1], x);else return min(val[p], suf(son[p][0], x));
}signed main() {int Q;scanf("%d", &Q);while(Q--) {int opt, x;scanf("%d%d", &opt, &x);if(opt == 1) ins(rt, x);else if(opt == 2) del(rt, x);else if(opt == 3) printf("%d\n", get_rank(rt, x));else if(opt == 4) printf("%d\n", kth(rt, x));else if(opt == 5) printf("%d\n", pre(rt, x));else if(opt == 6) printf("%d\n", suf(rt, x));}
}

二：FHQ Treap

支持：按权值 $v a l$ 分割（维护 $v a l$ 的有序性）、按排名即 $s i z e$ 分割（维护序列的有序性）、合并两颗树
??????插入、删除、查询 $x$ 的排名、查询排名为 $x$ 的数、查前驱、查后继
??????区间左移 —— HDU多校第九场 1007 Game —— 区间左移 + FHQ Treap

模板题：P3369 【模板】普通平衡树

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());struct Treap {const static int maxn = 1e5 + 5;int root, tot;int sz[maxn], val[maxn];int rd[maxn], son[maxn][2];void init() {fill(sz, sz+tot+1, 0);fill(son[0], son[0]+tot+1, 0);fill(son[1], son[1]+tot+1, 0);root = tot = 0;}Treap() {root = tot = 0;
//        srand(clock() + time(0));}inline void pushup(int x) {sz[x] = sz[son[x][0]] + sz[son[x][1]] + 1;}inline int new_node(int v) {sz[++tot] = 1, val[tot] = v, rd[tot] = rnd();return tot;}int merge(int x, int y) {if(!x || !y) return x + y;if(rd[x] < rd[y]) return son[x][1] = merge(son[x][1], y), pushup(x), x;else return son[y][0] = merge(x, son[y][0]), pushup(y), y;}void split_by_val(int now, int k, int &x, int &y) {if(!now) return x = y = 0, void();if(val[now] <= k) x = now, split_by_val(son[now][1], k, son[now][1], y);else y = now, split_by_val(son[now][0], k, x, son[now][0]);pushup(now);}void split_by_sz(int now, int k, int &x, int &y) {if(!now) return x = y = 0, void();if(sz[son[now][0]] >= k) y = now, split_by_sz(son[now][0], k, x, son[now][0]);else x = now, split_by_sz(son[now][1], k-sz[son[now][0]]-1, son[now][1], y);pushup(now);}void ins(int v) {int x, y; split_by_val(root, v, x, y);root = merge(merge(x, new_node(v)), y);}void del(int v) {int x, y, z; split_by_val(root, v, x, z);split_by_val(x, v-1, x, y);y = merge(son[y][0], son[y][1]);root = merge(merge(x, y), z);}inline int get_rank(int v) {int x, y, ret;split_by_val(root, v-1, x, y);ret = sz[x] + 1;root = merge(x, y);return ret;}inline int kth(int now, int k) {	//	查询排名while(true) {if(k <= sz[son[now][0]]) now = son[now][0];else if(k == sz[son[now][0]] + 1) return val[now];else k -= sz[son[now][0]] + 1, now = son[now][1];}}inline int pre(int v) {int x, y, ret;split_by_val(root, v-1, x, y);ret = kth(x, sz[x]);root = merge(x, y);return ret;}inline int suf(int v) {int x, y, ret;split_by_val(root, v, x, y);ret = kth(y, 1);root = merge(x, y);return ret;}
} T;signed main() {int Q;scanf("%d", &Q);while(Q--) {int opt, x;scanf("%d%d", &opt, &x);if(opt == 1) T.ins(x);else if(opt == 2) T.del(x);else if(opt == 3) printf("%d\n", T.get_rank(x));else if(opt == 4) printf("%d\n", T.kth(T.root, x));else if(opt == 5) printf("%d\n", T.pre(x));else if(opt == 6) printf("%d\n", T.suf(x));}
}

三：文艺平衡树

维护一个序列，实现区间翻转
模板题：P3391 【模板】文艺平衡树

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 5;
int b[maxn];struct Treap {const static int maxn = 5e5 + 5;int root, tot;int sz[maxn], val[maxn], lz[maxn];int rd[maxn], son[maxn][2];Treap() {root = tot = 0;}inline void init() {fill(sz, sz+tot+1, 0);fill(son[0], son[0]+tot+1, 0);fill(son[1], son[1]+tot+1, 0);root = tot = 0;}inline void pushup(int x) {sz[x] = sz[son[x][0]] + sz[son[x][1]] + 1;}inline void pushdown(int x) {swap(son[x][0], son[x][1]);if(son[x][0]) lz[son[x][0]] ^= 1;if(son[x][1]) lz[son[x][1]] ^= 1;lz[x] = 0;}int merge(int x, int y) {if(!x || !y) return x + y;if(rd[x] < rd[y]) {if(lz[x]) pushdown(x);return son[x][1] = merge(son[x][1], y), pushup(x), x;}else {if(lz[y]) pushdown(y);return son[y][0] = merge(x, son[y][0]), pushup(y), y;}}void split_by_sz(int now, int k, int &x, int &y) {if(!now) return x = y = 0, void();if(lz[now]) pushdown(now);if(sz[son[now][0]] >= k) y = now, split_by_sz(son[now][0], k, x, son[now][0]);else x = now, split_by_sz(son[now][1], k-sz[son[now][0]]-1, son[now][1], y);pushup(now);}void insert(int pos, int v) {int u = ++tot, x, y; val[u] = v, sz[u] = 1, rd[u] = rnd();split_by_sz(root, pos-1, x, y);root = merge(merge(x, u), y);}int dfs(int *a, int l, int r) {if(l > r) return 0;int u = ++tot, mid = l + r >> 1;val[u] = a[mid], sz[u] = r - l + 1, rd[u] = rnd();son[u][0] = dfs(a, l, mid-1); son[u][1] = dfs(a, mid+1, r);pushup(u); return u;}void build(int *a, int l, int r) {root = dfs(a, l, r);}void dfs_seq(int u, int *p) {if(u == 0) return;if(lz[u]) pushdown(u);dfs_seq(son[u][0], p);*(p + sz[son[u][0]] + 1) = val[u];dfs_seq(son[u][1], p+sz[son[u][0]]+1);}void seq(int *p) {dfs_seq(root, p);}inline int kth(int now, int k) {	//	查询排名while(true) {if(k <= sz[son[now][0]]) now = son[now][0];else if(k == sz[son[now][0]] + 1) return val[now];else k -= sz[son[now][0]] + 1, now = son[now][1];}}void reverse(int l, int r) {int L, R, l1, r1;split_by_sz(root, r, L, R);split_by_sz(L, l-1, l1, r1);lz[r1] ^= 1;root = merge(merge(l1, r1), R);}
} T;signed main() {int n, m, l, r;scanf("%d%d", &n, &m);
//	for(int i=1; i<=n; i++) T.insert(i, i);for(int i=1; i<=n; i++) b[i] = i;T.build(b, 1, n);while(m--) {scanf("%d%d", &l, &r);T.reverse(l, r);}T.seq(b);for(int i=1; i<=n; i++) printf("%d%c", b[i], " \n"[i==n]);
}