前言

暑假集训的时候学了很多新的东西，但是都不好专门去分开写，所以整合到了一起。

由于这些算法技巧性较强，大多是基于先前算法的，所以叫技巧性知识总结。

可撤销并查集

众所周知，传统的并查集只能支持将两个连通块合并，但是在某些情形下我们需要撤销并查集上的一些操作，也就是进行删边操作。这种时候可能就会有大神要用可持久化并查集了，但是实际上单纯的进行删边操作并不需要如此大费周章，只需要使用可撤销并查集即可。

可撤销并查集。可以支持加边操作，以及根据操作从后往前进行删边。它的用途是比可持久化并查集小的，但是要简单的多。

我们考虑在每一次进行合并操作的时候记录下当前被合并（也就是改变了父亲的）的节点，把它放到一个栈里；当要进行撤销操作的时候，就弹出栈顶节点，将它的父亲改成自己，并删除原父亲上的一些信息（例如大小等）。

代码如下：

int fa[Maxn], siz[Maxn];
int s[Maxn], top;

void init() {
	top = 0;
	for(int i = 1; i <= n; i++) {
		fa[i] = i;
		siz[i] = 1;
	} 
}

int find(int x) {
	return fa[x] == x ? x : find(fa[x]);
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx == fy) {
		return ;
	}
	if(siz[fx] < siz[fy]) swap(fx, fy);
	fa[fy] = fx;
	siz[fx] += siz[fy];
	s[++top] = fy; //记录节点
}

void back(int x) {
	while(top > x) {
		int p = s[top--];
		siz[fa[p]] -= siz[p];//删除信息
		fa[p] = p;//改父亲
	}
}

珂朵莉树

珂朵莉树实际上是一种相当暴力的数据结构，它基于 STL 中的 set 实现。在数据随机的情况下，它进行区间覆盖和其他操作的均摊复杂度是 \(O(n\log n)\) 的。

考虑到区间覆盖后整个区间相当于被分成了几段颜色相同的段，那么我们就在 set 中维护这些信息。珂朵莉树上的每一个节点定义为 \((l,r,v)\)，表示区间 \([l,r]\) 的颜色全为 \(v\)。

考虑区间覆盖怎样做，实际上可以分成下列三种操作：

• 将 \(l,r\) 两个端点从以前的整区间内分裂出来。
• 将 \([l,r]\) 区间内所有块删去。
• 加入块 \((l,r,v)\)。

对于第一个操作，我们利用函数 Split(x) 实现，表示将包含 \(x\) 的块 \((l,r,v)\) 分裂成 \((l,x-1,v)\) 和 \((x,r,v)\)。这个利用二分查找就可以简单实现，代码如下：

auto split(int x) {
    auto it = s.lower_bound({x, 0, 0});//二分查找
    if(it -> l == x) {
        return it;
    }
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    s.erase(it);
    s.insert({l, x - 1, v});
    return s.insert({x, r, v}).first;//返回地址
}

注意 Split 完要返回 \((x,r,v)\) 这个块的地址，方便接下来的操作。然后两个操作我们使用 Assign(l, r) 实现，只需要先 Split，然后删除两个端点间的所有块，最后插入即可。代码如下：

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);//分裂
    //注意分裂顺序一定不能改，否则可能会 RE
    s.erase(itl, itr);//直接利用地址删除即可
    s.insert({l, r, v});//插入
}

上面就是珂朵莉树的基本函数，对于其他的区间操作，与 Assign 操作是类似的，先分裂区间再处理即可。

根号分治

实际上根号分治完全就是一个很牛的 trick，我们用下面一道例题引入：

给定一个序列 \(a\)，需要支持两种操作：

• 1 x y：将 \(a_x\) 加上 \(y\)。
• 2 x y：询问所有下标 \(i\) 满足 \(i\equiv y\pmod x\) 的 \(a_i\) 之和。

乍一看十分难做，不过我们容易想到下面两种暴力做法：

• 暴力模拟，操作一直接操作，操作二直接暴力跳所有下标并求和。这样复杂度分别是 \(O(1)\) 和 \(O(n)\) 的。
• 预处理，记录一个数组 \(b_{i,j}\)，表示所有下标模 \(x\) 等于 \(y\) 的值的和。操作一直接操作，接下来暴力维护 \(b\) 数组，操作二直接查询。复杂度分别是 \(O(n)\) 和 \(O(1)\) 的。

不难发现上面两个做法都有些极端，一个 \(O(1)\) 一个 \(O(n)\)，如果我们能够将两种暴力均摊一下，是否可以优化复杂度呢？

考虑去设定一个阈值 \(b\)。当操作的数 \(\le b\) 的时候，使用暴力 \(2\) 的方法维护 \(b\) 数组，此时复杂度应该是 \(O(b)\) 的；而当操作的数 \(>b\) 的时候，使用暴力 \(1\) 的方法跳数组，这样最多跳 \(\lceil\frac nb\rceil\) 次，复杂度就是 \(O(\frac nb)\) 的。

那么两者综合起来的复杂度就是 \(O(q(b+\frac nb))\) 的，由基本不等式得，当 \(b\) 取 \(\sqrt n\) 时有最优复杂度，为 \(O(q\sqrt n)\)。由于其阈值取到了 \(\sqrt n\)，相当于在 \(\sqrt n\) 处分开处理，因此得名根号分治。

操作分块

分块思想我们并不陌生，在序列上分块的本质就是控制暴力统计的数量，剩余部分整体处理。而实际上，我们可以将这种思想运用到操作序列中；当答案具有可合并性，修改询问不复杂的时候可以考虑操作分块。

操作分块的核心其实就是在操作序列上分块，而它的核心在于：我们每一次对一整个块进行操作的时候，已经处理完了该块之前的询问的答案和操作的贡献。而对于块中的贡献，我们暴力枚举每一个询问，接下来再暴力枚举每一个操作，计算这些操作另外的贡献。最后再将这些贡献传递给下一个块。

不难发现，操作中我们需要暴力去看块中的贡献，这一部分复杂度是 \(O(B^2)\) 的。而当我们分块之后这个复杂度就可以降到 \(O(q)\) 了。而如果前面的块产生的贡献都可以快速计算的话，总复杂度就可以达到 \(O(q\sqrt q)\)。此时再在上面适当加一些数据结构就没有那么紧张了。

连续段 dp

在一类序列计数的问题中，我们状态的转移可能会与相邻的已插入元素的值紧密相关，只有知道其值才能求解。而如果此时在只考虑往序列两端插入的情况下，问题将变得容易解决的时候，就可以利用连续段 dp。

连续段 dp 的操作利用了在序列两端进行操作的优秀性质，其插入操作也只会在序列两端进行。我们可以在整个序列上去考虑插入操作，不难发现，对于一个局部状态，其一定呈现为一段一段的样子。那么此时再插入一个元素就只会存在三种可能：

• 新建了一个连续段。
• 贴在另一个连续段上。
• 将两个连续段连接起来。

于是设 \(dp(i,j)\) 表示当前插入了 \(i\) 个元素，且连续段数量为 \(j\) 的方案数。那么根据上面所说，转移就只有三种情况：

• 新建连续段：\(f(i,j)\times (j+1)\to f(i+1,j+1)\)。\(j+1\) 表示在 \(j\) 个连续段之间插入的方案数。
• 贴在连续段上：\(f(i,j)\times 2j\to f(i+1,j)\)。\(2j\) 表示总共 \(j\) 个连续段，每个连续段有两个端点。
• 合并两个连续段：\(f(i,j)\times(j-1)\to f(i+1,j-1)\)。\(j-1\) 表示在 \(j\) 个连续段之间合并的方案数。

接着 \(O(n^2)\) 转移即可。剩下的状态就因题而异了。