平衡树学习笔记

其实是学过的，然后，就忘了......
本文介绍 Splay/Link Cut Tree/FHQ Treap 三种平衡树相关的数据结构。

Splay

Splay 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。

变量信息

struct Splay {
	int rt, tot, f[N], ch[N][2], a[N], c[N], s[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
};

维护操作

$\operatorname{upd}(p)$

更新 $s_p$。

	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]

$\operatorname{get}(p)$

判断 $p$ 是 $f_p$ 的左儿子还是右儿子。

	#define get(p) (p == ch[f[p]][1])

$\operatorname{clr}(p)$

销毁 $p$。

	#define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0

$\operatorname{rot}(p)$

将 $p$ 旋转上移一个位置。

	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y)) ch[y][v] = p;
	}

$\operatorname{splay}(p, g)$

这是 splay 中最重要的操作。

将 $p$ 旋转为 $g$ 的儿子（若 $g$ 为 $0$ 则旋转为根）。

	inline void splay(int p, int g = 0) {
		for (int x = f[p]; (x = f[p]) != g; rot(p))
			if (f[x] != g) rot(get(p) == get(x) ? x : p);
		if (!g) rt = p;
	}

访问操作

$\operatorname{ins}(k)$

插入 $k$。

	inline void ins(int k) {
		if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
		int x = rt, y = 0;
		while (1) {
			if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
			y = x, x = ch[x][a[x]<k];
			if (!x) {
				a[++tot] = k, c[tot] = s[tot] = 1;
				f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
				return splay(tot);
			}
		}
	}

$\operatorname{rnk}(k)$

查询 $k$ 的排名（$<k$ 的数的个数 $+1$）。

	inline int rnk(int k) {
		int p = rt, x = 0;
		while (1)
			if (k < a[p]) {
				if (!lc) return splay(p), x + 1;
				p = lc;
			} else {
				x += s[lc];
				if (k == a[p]) return splay(p), x + 1;
				x += c[p];
				if (!rc) return splay(p), x + 1;
				p = rc;
			}
	}

$\operatorname{kth}(k)$

查询排名为 $k$ 的数。

	inline int kth(int k) {
		int p = rt;
		while (1)
			if (k <= s[lc]) p = lc;
			else {
				k -= s[lc];
				if (k <= c[p]) return splay(p), a[p];
				k -= c[p], p = rc;
			}
	}

$\operatorname{pre}(k)$

查询 $k$ 的前驱（$<k$ 的最大的数）。

	inline int pre(int k) {
		return kth(rnk(k) - 1);
	}

$\operatorname{nxt}(k)$

查询 $k$ 的后继（$>k$ 的最小的数）。

	inline int nxt(int k) {
		return kth(rnk(k + 1));
	}

$\operatorname{del}(k)$

删除 $k$（如果没有则跳过）。

	inline void del(int k) {
		rnk(k);
		if (k != a[rt]) return;
		if (c[rt] > 1) return --c[rt], --s[rt], void();
		int p = rt;
		if (!lc && !rc) return rt = 0, clr(p), void();
		if (!lc || !rc) return f[rt=lc+rc] = 0, clr(p), void();
		return pre(k), f[rc] = rt, ch[rt][1] = rc, clr(p), --s[rt], void();
	}

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

const int N = 1e5 + 7;

struct Splay {
	int rt, tot, f[N], ch[N][2], a[N], c[N], s[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
	#define get(p) (p == ch[f[p]][1])
	#define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y)) ch[y][v] = p;
	}
	inline void splay(int p, int g = 0) {
		for (int x = f[p]; (x = f[p]) != g; rot(p))
			if (f[x] != g) rot(get(p) == get(x) ? x : p);
		if (!g) rt = p;
	}
	inline void ins(int k) {
		if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
		int x = rt, y = 0;
		while (1) {
			if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
			y = x, x = ch[x][a[x]<k];
			if (!x) {
				a[++tot] = k, c[tot] = s[tot] = 1;
				f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
				return splay(tot);
			}
		}
	}
	inline int rnk(int k) {
		int p = rt, x = 0;
		while (1)
			if (k < a[p]) {
				if (!lc) return splay(p), x + 1;
				p = lc;
			} else {
				x += s[lc];
				if (k == a[p]) return splay(p), x + 1;
				x += c[p];
				if (!rc) return splay(p), x + 1;
				p = rc;
			}
	}
	inline int kth(int k) {
		int p = rt;
		while (1)
			if (k <= s[lc]) p = lc;
			else {
				k -= s[lc];
				if (k <= c[p]) return splay(p), a[p];
				k -= c[p], p = rc;
			}
	}
	inline int pre(int k) {
		return kth(rnk(k) - 1);
	}
	inline int nxt(int k) {
		return kth(rnk(k + 1));
	}
	inline void del(int k) {
		rnk(k);
		if (k != a[rt]) return;
		if (c[rt] > 1) return --c[rt], --s[rt], void();
		int p = rt;
		if (!lc && !rc) return rt = 0, clr(p), void();
		if (!lc || !rc) return f[rt=lc+rc] = 0, clr(p), void();
		return pre(k), f[rc] = rt, ch[rt][1] = rc, clr(p), --s[rt], void();
	}
} splay;

int main() {
	int n;
	rd(n);
	for (int i = 1, o, x; i <= n; i++) {
		rd(o), rd(x);
		switch (o) {
			case 1 : splay.ins(x); break;
			case 2 : splay.del(x); break;
			case 3 : print(splay.rnk(x)); break;
			case 4 : print(splay.kth(x)); break;
			case 5 : print(splay.pre(x)); break;
			case 6 : print(splay.nxt(x)); break;
		}
	}
	return 0;
}

【模板】P3391 【模板】文艺平衡树

const int N = 1e5 + 7;
int n, m;

struct Splay {
	int rt, tot, f[N], ch[N][2], a[N], c[N], s[N], v[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
	#define get(p) (p == ch[f[p]][1])
	#define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
	#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
	inline void spd(int p) {
		if (p && v[p]) {
			if (lc) rev(lc);
			if (rc) rev(rc);
			v[p] = 0;
		}
	}
	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y)) ch[y][v] = p;
	}
	inline void splay(int p, int g = 0) {
		for (int x = f[p]; (x = f[p]) != g; rot(p))
			if (f[x] != g) rot(get(p) == get(x) ? x : p);
		if (!g) rt = p;
	}
	inline void ins(int k) {
		if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
		int x = rt, y = 0;
		while (1) {
			if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
			y = x, x = ch[x][a[x]<k];
			if (!x) {
				a[++tot] = k, c[tot] = s[tot] = 1;
				f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
				return splay(tot);
			}
		}
	}
	inline int kth(int k) {
		int p = rt;
		while (1) {
			spd(p);
			if (k <= s[lc]) p = lc;
			else {
				k -= s[lc];
				if (k <= c[p]) return splay(p), p;
				k -= c[p], p = rc;
			}
		}
	}
	inline void work(int l, int r) {
		l = kth(l - 1), r = kth(r + 1), splay(l), splay(r, l), rev(ch[r][0]);
	}
	void dfs(int p) {
		spd(p);
		if (lc) dfs(lc);
		if (a[p] && a[p] <= n) print(a[p], ' ');
		if (rc) dfs(rc);
	}
} splay;

int main() {
	rd(n), rd(m);
	for (int i = 0; i <= n + 1; i++) splay.ins(i);
	for (int i = 1, l, r; i <= m; i++) rd(l), rd(r), splay.work(l + 1, r + 1);
	splay.dfs(splay.rt);
	return 0;
}

Link Cut Tree

Link Cut Tree (LCT) 是一种数据结构，我们用它来解决动态树问题。Splay 是 LCT 的基础，但是 LCT ⽤的 Splay 和普通的 Splay 在细节处不太一样（进行了一些扩展）。

LCT 的主要结构

LCT 由多个 Splay 构成，维护一个树，树的每个节点与所有 Splay 节点一一对应。

树的每条边分为实边和虚边。

对于实边，每一个 Splay 通过其中序遍历维护一条从上到下在原树中的深度严格递增的实链。

对于虚边，各个 Splay 之间并不是独立的。每个 Splay 的根节点的父亲节点本应是空，但在 LCT 中每个 Splay 的根节点的父亲节点指向原树中这条实链的最顶端的点的父亲节点。每个这样的指向对应了原树中的一条虚边，其特点在于认父不认子。因此，每个连通块恰好有一个点的父亲节点为空。

变量信息

struct LCT {
	int f[N], ch[N][2], s[N], v[N], a[N], c[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
};

维护操作

$\operatorname{upd}(p)$

更新 $s_p$ 和 $c_p$。

	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]

$\operatorname{get}(p)$

判断 $p$ 是 $f_p$ 的左儿子还是右儿子。

	#define get(p) (p == ch[f[p]][1])

$\operatorname{rev}(p)$

翻转 $p$。

	#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])

$\operatorname{isrt}(p)$

判断 $p$ 是否为所在 Splay 的根。

	#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)

$\operatorname{spd}(p)$

下传 $v_p$。

	inline void spd(int p) {
		if (p && v[p]) {
			if (lc) rev(lc);
			if (rc) rev(rc);
			v[p] = 0;
		}
	}

$\operatorname{rot}(p)$

将 $p$ 旋转上移一个位置。

	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y) && !o) ch[y][v] = p;
	}

$\operatorname{pre}(p)$

$\operatorname{splay}(p)$ 之前的准备工作，要把路径上的点都 $\operatorname{spd}(p)$ 一下。

	void pre(int p) {
		if (!isrt(p)) pre(f[p]);
		spd(p);
	}

$\operatorname{splay}(p)$

将 $p$ 旋转为所在 Splay 的根。

	inline void splay(int p) {
		pre(p);
		for (int x = f[p]; !isrt(p); rot(p), x = f[p])
			if (!isrt(x)) rot(get(p) == get(x) ? x : p);
	}

$\operatorname{access}(p)$

这是 LCT 中最重要的操作。

把从原树的根到 $p$ 的路径拉成一条实链放到一个 Splay 里。

	inline void access(int p) {
		for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
	}

$\operatorname{mkrt}(p)$

使 $p$ 直接成为原树的根。

	inline void mkrt(int p) {
		access(p), splay(p), rev(p);
	}

$\operatorname{split}(x, y)$

把原树中 $x,y$ 之间的路径拉成一条实链放到一个 Splay 里（同时使 $y$ 成为原树的根）。

	inline void split(int x, int y) {
		mkrt(x), access(y), splay(y);
	}

访问操作

$\operatorname{fdrt}(p)$

找到 $p$ 所在的原树的根。

	inline int fdrt(int p) {
		access(p), splay(p);
		while (lc) spd(p), p = lc;
		return splay(p), p;
	}

$\operatorname{link}(x, y)$

在原树的 $x,y$ 两点间连一条边（若已经连通则不连）。

	inline bool link(int x, int y) {
		mkrt(x);
		return fdrt(y) != x && (f[x] = y);
	}

$\operatorname{cut}(x, y)$

将原树的 $x,y$ 两点间的边删掉（若不存在则不删）。

	inline bool cut(int x, int y) {
		mkrt(x);
		if (fdrt(y) != x || s[x] != 2) return 0;
		return f[y] = ch[x][1] = 0, upd(x), 1;
	}

$\operatorname{chg}(p, x)$

将 $p$ 的点权修改为 $x$。

	inline void chg(int p, int x) {
		mkrt(p), a[p] = x, upd(p);
	}

【模板】P3690 【模板】Link Cut Tree （动态树）

const int N = 1e5 + 7;
int n, m;

struct LCT {
	int f[N], ch[N][2], s[N], v[N], a[N], c[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]
	#define get(p) (p == ch[f[p]][1])
	#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
	#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
	inline void spd(int p) {
		if (p && v[p]) {
			if (lc) rev(lc);
			if (rc) rev(rc);
			v[p] = 0;
		}
	}
	inline void rot(int p) {
		int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
		f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
		f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
		if ((f[p] = y) && !o) ch[y][v] = p;
	}
	void pre(int p) {
		if (!isrt(p)) pre(f[p]);
		spd(p);
	}
	inline void splay(int p) {
		pre(p);
		for (int x = f[p]; !isrt(p); rot(p), x = f[p])
			if (!isrt(x)) rot(get(p) == get(x) ? x : p);
	}
	inline void access(int p) {
		for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
	}
	inline void mkrt(int p) {
		access(p), splay(p), rev(p);
	}
	inline void split(int x, int y) {
		mkrt(x), access(y), splay(y);
	}
	inline int fdrt(int p) {
		access(p), splay(p);
		while (lc) spd(p), p = lc;
		return splay(p), p;
	}
	inline bool link(int x, int y) {
		mkrt(x);
		return fdrt(y) != x && (f[x] = y);
	}
	inline bool cut(int x, int y) {
		mkrt(x);
		if (fdrt(y) != x || s[x] != 2) return 0;
		return f[y] = ch[x][1] = 0, upd(x), 1;
	}
	inline void chg(int p, int x) {
		mkrt(p), a[p] = x, upd(p);
	}
} lct;

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) rd(lct.a[i]), lct.c[i] = lct.a[i], lct.s[i] = 1;
	for (int i = 1, o, x, y; i <= m; i++) {
		rd(o), rd(x), rd(y);
		switch (o) {
			case 0 : lct.split(x, y), print(lct.c[y]); break;
			case 1 : lct.link(x, y); break;
			case 2 : lct.cut(x, y); break;
			case 3 : lct.chg(x, y); break;
		}
	}
	return 0;
}

常见应用

1. 维护链信息（平衡树操作）
2. 动态维护连通性 & 边双联通分量（可以说是并查集的升级，因为并查集只能连不能断）
3. 维护边权（将边当成点进行操作，常用于维护生成树）
4. 维护子树信息

维护子树信息

有时候，我们需要的并不是维护链的信息，而是子树的信息。要知道，LCT 强于维护链的信息，而弱于维护子树的信息。然而动态的连边和断边，又不得不要求我们使用 LCT 来维护。

我们已经可以通过 Splay 来获知实子树（也就是原树中的一条链）的信息总和，现在只需要维护虚子树的信息总和，然后两者相加即可。

讨论一下 LCT 中的每个操作会对虚实边产生怎样的影响，结果你会惊奇的发现，只有 $\operatorname{access}(p)$ 和 $\operatorname{link}(p)$ 需要进行小小的修改就能轻松的维护了。

FHQ Treap

Treap 是一种弱平衡的二叉搜索树。Treap 这个单词是 Tree 和 Heap 的组合，表明 Treap 是一种由树和堆组合形成的数据结构。Treap 除了本身储存的值要满足二叉搜索树的性质之外，每个结点上要额外储存一个值，这个值需满足大根堆的性质。而这个额外的值是每个结点建立时随机生成的，因此 Treap 是期望平衡的。

Treap 分为旋转式和无旋式两种，FHQ Treap 即无旋式 Treap。FHQ Treap 的操作方式使得它天生支持维护序列、可持久化等特性，从而使这个东西严格意义上吊打无旋式 Treap 和 Splay，它们能搞的事情 FHQ Treap 都能搞。

变量信息及基本维护操作

struct Treap {
	int rt, tot, ch[N][2], a[N], d[N], s[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
	#define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
} treap;

维护操作

FHQ Treap 的维护操作仅有两个，分裂 (split) 与合并 (merge)。

分裂 (split)

分裂过程接受两个参数：根指针 $p$ 和关键值 $k$。结果为将根指针指向的 Treap 分裂为两个 Treap，第一个 Treap 所有结点的关键值小于等于 $k$，第二个 Treap 所有结点的关键值大于 $k$。

	inline void split(int p, int k, int &x, int &y) {
		if (!p) return x = y = 0, void();
		if (a[p] <= k) x = p, split(rc, k, rc, y);
		else y = p, split(lc, k, x, lc);
		upd(p);
	}

合并 (merge)

合并过程接受两个参数：左 Treap 的根指针 $x$、右 Treap 的根指针 $y$，必须满足 $x$ 中所有结点的关键值小于等于 $y$ 中所有结点的关键值。因为两个 Treap 已经有序，我们只需要考虑额外的随机值来决定哪个 Treap 应与另一个 Treap 的儿子合并。

	inline int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
		return ch[x][1] = merge(ch[x][1], y), upd(x), x;
	}

访问操作

$\operatorname{ins}(k)$

插入 $k$。

	inline void ins(int k) {
		a[++tot] = k, s[tot] = 1, d[tot] = rand();
		if (!rt) return rt = tot, void();
		int x, y;
		split(rt, k, x, y), rt = merge(merge(x, tot), y);
	}

$\operatorname{rnk}(k)$

查询 $k$ 的排名（$<k$ 的数的个数 $+1$）。

	inline int rnk(int k) {
		int x, y, ret;
		return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
	}

$\operatorname{kth}(k)$

查询排名为 $k$ 的数。

	inline int kth(int k) {
		int p = rt;
		while (1)
			if (k <= s[lc]) p = lc;
			else {
				k -= s[lc] + 1;
				if (!k) return a[p];
				p = rc;
			}
	}

$\operatorname{pre}(k)$

查询 $k$ 的前驱（$<k$ 的最大的数）。

	inline int pre(int k) {
		return kth(rnk(k) - 1);
	}

$\operatorname{nxt}(k)$

查询 $k$ 的后继（$>k$ 的最小的数）。

	inline int nxt(int k) {
		return kth(rnk(k + 1));
	}

$\operatorname{del}(k)$

删除 $k$（如果没有则跳过）。

	inline void del(int k) {
		int x, y, z;
		split(rt, k, x, z), split(x, k - 1, x, y);
		rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
		clr(y);
	}

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

const int N = 1e5 + 7;

struct Treap {
	int rt, tot, ch[N][2], a[N], d[N], s[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
	#define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
	inline void split(int p, int k, int &x, int &y) {
		if (!p) return x = y = 0, void();
		if (a[p] <= k) x = p, split(rc, k, rc, y);
		else y = p, split(lc, k, x, lc);
		upd(p);
	}
	inline int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
		return ch[x][1] = merge(ch[x][1], y), upd(x), x;
	}
	inline void ins(int k) {
		a[++tot] = k, s[tot] = 1, d[tot] = rand();
		if (!rt) return rt = tot, void();
		int x, y;
		split(rt, k, x, y), rt = merge(merge(x, tot), y);
	}
	inline int rnk(int k) {
		int x, y, ret;
		return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
	}
	inline int kth(int k) {
		int p = rt;
		while (1)
			if (k <= s[lc]) p = lc;
			else {
				k -= s[lc] + 1;
				if (!k) return a[p];
				p = rc;
			}
	}
	inline int pre(int k) {
		return kth(rnk(k) - 1);
	}
	inline int nxt(int k) {
		return kth(rnk(k + 1));
	}
	inline void del(int k) {
		int x, y, z;
		split(rt, k, x, z), split(x, k - 1, x, y);
		rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
		clr(y);
	}
} treap;

int main() {
	int n;
	rd(n), treap.ins(-1e9), treap.ins(1e9); 
	for (int i = 1, o, x; i <= n; i++) {
		rd(o), rd(x);
		switch (o) {
			case 1 : treap.ins(x); break;
			case 2 : treap.del(x); break;
			case 3 : print(treap.rnk(x) - 1); break;
			case 4 : print(treap.kth(x + 1)); break;
			case 5 : print(treap.pre(x)); break;
			case 6 : print(treap.nxt(x)); break;
		}
	}
	return 0;
}

【模板】P3391 【模板】文艺平衡树

const int N = 1e5 + 7;
int n, m;

struct Treap {
	int rt, tot, ch[N][2], a[N], d[N], s[N], v[N];
	#define lc ch[p][0]
	#define rc ch[p][1]
	#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
	#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
	inline void spd(int p) {
		if (p && v[p]) {
			if (lc) rev(lc);
			if (rc) rev(rc);
			v[p] = 0;
		}
	}
	inline void split(int p, int k, int &x, int &y) {
		if (!p) return x = y = 0, void();
		spd(p);
		if (s[lc] < k) x = p, k -= s[lc] + 1, split(rc, k, rc, y);
		else y = p, split(lc, k, x, lc);
		upd(p);
	}
	inline int merge(int x, int y) {
		if (!x || !y) return x | y;
		spd(x), spd(y);
		if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
		return ch[x][1] = merge(ch[x][1], y), upd(x), x;
	}
	inline void ins(int k) {
		a[++tot] = k, s[tot] = 1, d[tot] = rand();
		if (!rt) return rt = tot, void();
		int x, y;
		split(rt, k, x, y), rt = merge(merge(x, tot), y);
	}
	inline void work(int l, int r) {
		int x, y, z;
		split(rt, r, x, z), split(x, l - 1, x, y);
		rev(y), merge(merge(x, y), z);
	}
	void dfs(int p) {
		spd(p);
		if (lc) dfs(lc);
		if (a[p] && a[p] <= n) print(a[p], ' ');
		if (rc) dfs(rc);
	}
} treap;

int main() {
	rd(n), rd(m);
	for (int i = 0; i <= n + 1; i++) treap.ins(i);
	for (int i = 1, l, r; i <= m; i++) rd(l), rd(r), treap.work(l + 1, r + 1);
	treap.dfs(treap.rt);
	return 0;
}

参考资料

• OI Wiki Splay
• OI Wiki Link Cut Tree
• FlashHu LCT总结——概念篇+洛谷P3690[模板]Link Cut Tree(动态树)（LCT，Splay）
• FlashHu LCT总结——应用篇（附题单）（LCT）
• OI Wiki Treap
• _Mocha_ Fhq-Treap总结：短小精悍不旋转的神级数据结构