数据结构的一些小 trick。
并查集
支持撤销
每次合并的时候按照集合的大小进行启发式合并，并且用一个操作栈记录本次操作。
在撤销一次操作的时候，只需要按照记录还原并查集即可。
合并查询操作单次 \(O(\log n)\)，撤销操作单次 \(O(1)\)。这种并查集在一些离线算法下有大用处。
维护不可逆的覆盖操作
考虑这么一道题目：给一棵 \(n\) 个点的树，有 \(m\) 次操作，每次操作会把一条路径上的点染色，且颜色会覆盖之前染的颜色，求最后每个点的颜色，不强制在线。\(n\leq 10^6,m\leq 5\times 10^6\)。
一种 naive 的思想是用树链剖分和线段树维护颜色，但是这样是 \(m\log^2 n\) 的。
考虑把操作倒序，那么每次执行的是不可逆的染色操作。
对每个点维护并查集，表示它到根路径上第一个需要被染色的点是什么，一开始显然指向自己。
如果一个点被染色了，那么就把它的边连向它父亲。每次染色就直接按照并查集的链接暴力跳，然后染色即可。
因为每个点最多被染色一次，在并查集使用 \(n\alpha(n)\) 复杂度的版本下，总复杂度仅为 \(O(n\alpha(n))\)。
这个 trick 虽然可能不会单独成题，但是可能会被穿插到一些题目中。它对复杂度的优化还是挺大的。
栈
对顶栈
例题：你需要动态维护一个长度为 \(n\) 序列，有 \(q\) 个操作，每个操作为头尾加删元素或查询一些信息。
假设只能从尾部加删，那么我们就可以维护一个类似于栈的东西，每次加进来一个就把它压入栈，并更新一些信息，删掉一个就把它从栈弹掉，并把信息复原。
现在我们两头都要支持加删，一种直接的想法是维护两个栈，并且把它们的栈底顶到一起，这样头尾加删和普通的加删就没有什么区别，只有查询的时候需要额外计算跨过两个栈的贡献。
但是这样会出现一个问题，可能有一次删除会把一个栈的栈底给删了，这样原先的结构就被破坏了，这是很麻烦的。但实际上只需要再从序列中间开始，重新构造两个栈就可以了，这样总的重新构造的点的数目的上限是 \(\max(n,q)\) 的。
因为维护了这两个栈的顶着的，所以我们称它为对顶栈。
好像这种套路就能干这一件事情，博主也就在某次考试中遇到了一次，不过了解一下它的思想总是好的。
2048 栈
因为没得名字，随手取了一个。（侵删）
当你需要动态维护一个不好加入元素的东西的时候（如 AC 自动机、凸包等），你就可以用这个 trick，花费额外的一个 \(\log\) 的代价去较为方便的维护它。
这里就用 AC 自动机举例。
维护一个栈，每个栈内的元素都是一个 AC 自动机，并且记录下 AC 自动机内的字符串数目。
对于一次加入，就在栈顶加入一个新的 AC 自动机，内部保存这一次加入的这一个字符串。
如果此时栈顶的两个 AC 自动机内的字符串数目相同，就把这两个 AC 自动机合并，并且建出一个新的 AC 自动机，一直这样直到栈顶的两个 AC 自动机不满足这个条件。
不难发现，每次更新栈的时候，AC 自动机的大小就像 2048 一样，相同即合并，且都是 \(2\) 的倍数。故每个字符串只会在它所在的 AC 自动机的大小为 \(2^k\) 的时候有一个贡献，所以总复杂度是总长度乘上 \(\log\) 字符串个数的。
特别的，这个 trick 是可以在线维护的。
boshi 提供了一个题目 CF710F 。
线段树
时间和序列的对调
一般线段树都是维护的序列信息，如区间和，区间积。
但是在某些问题中，它的操作是区间修改，查询是单点查询，这时候就有一个对调时间和序列的 trick 。
正如 trick 的名字，我们把时间和序列对调，每次一步一步地在序列上面走，同时对时间维护线段树。
那么对于对调前的区间修改，现在就变成了两个单点的修改，对于对调前的查询，现在就变成了一个前缀的查询。
在某些方便不维护前者，而较方便维护后者的题目中，这个 trick 是非常实用的。
比如说 某场公开的考试题。
懒信息
也是随手取的名字，其实这个 trick 挺常见的。（侵删）
懒标记是不下传的标记，懒信息就是查询的时候不合并的信息。
在一些题目中，对于查询操作，如果各个区间的信息是独立的（也就是说并不需要把区间信息合并就可以得到答案），且合并区间信息的复杂度远大于通过单个区间的信息得到答案的复杂度，就可以把信息懒化。
例题：维护一个序列，支持两个操作：往后面加一个数，查询 \(x\) 在区间 \([l,r]\) 的排名，操作数 \(\leq 10^5\)，保证查询的时候序列长度大于等于 \(r\)，强制在线。
先设操作数为 \(n\)，序列可能有 \(n\) 这么长，所以先开一个长度为 \(n\) 的线段树。
每个点维护一个有序的序列，表示它控制区间内的数排序之后的结果。
不难发现每层最多 \(n\) 个数，一共 \(\log n\) 层，所以空间复杂度 \(n \log n\)。
对于每次往后面加数，就把对应位置的数进行更改，并且往上更新，更新的规则是这样的：如果一个点的儿子是满的，那么就更新它，否则就不更新它。
更新的时候可以使用归并排序，复杂度是 \(O(len)\) 的，因为更新的规则，每个点只会被更新一次，复杂度也是 \(O(n\log n)\) 的。
对于查询，naive 的方法是把查询定位到的区间归并，然后看 \(x\) 的排名，这样复杂度又回去了。
因为 \(x\) 的排名就是 \(x\) 前面有多少个数，所以我们没必要把查询定位到的区间合并，直接在每个定位到的区间内查询有多少个数小于 \(x\) 即可。使用二分复杂度就是 \(O(n\log^2 n)\)。
更加复杂一点的还有 UOJ #46。
平衡树
替罪羊树
trick 不是这个数据结构，而是它拍扁重构的思想。
如果你要动态维护一棵树，而且想要让它尽量的平衡（树高在 \(O(\log)\) 级别），那么就可以通过控制平衡因子拍扁重构。
比较经典的是动态加点，动态维护点分树。因为点分树如果要保证复杂度，需要树高在 \(O(\log)\) 级别，而动态加点并不好维护。那么我们就干脆在每次加点的时候，就把这个点看做一个子分治中心，并连向父亲。然后像替罪羊一样，如果某个子树太难看了，就直接拍扁重建。
比较经典的莫过于 [WC2014]紫荆花之恋 了。
根号算法
根号分治
应该是一个比较普及的 trick。
差不多就是小于根号的暴力也无所谓，大于根号的也就根号个东西。
比如出现次数大于根号的数不超过根号个，图中度数大于根号的点不超过根号个等。
这个 trick 比较简单，但是也容易被忽视，注意一下就可以了。
这方面的话可能比较简单，哈希冲突 是一个比较好的例子。
时间分块
似乎对时间轴操作的 trick 都挺重要的。
如标题所说，就是把所有的操作按照时间分块，那么在块的内部就有一个很好的性质：时间线的变动量不超过块大小。所以就可以在块内按照其它东西排序，对于询问就只需要动时间线，可能会更加方便。
比如说 [APIO2019]桥梁。
当然，一些其它的题目也可以用这个思想，可以把时间线的变动看做是别的东西的变动，比如 [HNOI2016]最小公倍数。
操作分块（定期重构）
也是一个比较妙的 trick。
在一些题目中，如果操作不好应用于序列，且很多个操作可以放一起修改序列，且操作对查询的影响比较好求，就可以用这个 trick。
这个 trick 的意思是先把所有的操作屯着，查询的时候可以先在原序列查，然后再去屯着的操作里面查。当屯着的操作达到一个上限的时候，就把它们一起放出来，把整个序列翻新一次。
这个 trick 也不常见，不过其思想也十分有意义。
其它
树的坐标表示
其实也不是什么高科技，也就标题唬人。
把树上每个点的坐标看做是 \((dfn,dep)\)。
这样的话，一个子树就代表着一个只有左右边界上下无界的矩形，子树内离当前点距离为某个范围内的点就对应着一个矩形，我们就可以把树上问题转化成二维平面上问题。
这道题 是个不错的例子。