CSP 2019 集训 搜索和数据结构

解题技巧

打表

完美数

输出区间完美数数量。

判断一个数是不是完美数是容易的。要求区间完美数数量，其实就是要快速算出前缀和。

前缀和……是不是类似于阶乘？

分段打表！打表间隔 $10^6$ 就可以了。

搜索

剪枝

虫食算

从低位向高位搜索，因为低位没有未确定的进位。

确定了一列的值之后马上验证。

枚举整数的顺序的话……比较玄学地从大到小？

另外据说这题的正解是高斯消元？

整数分解

重点是“不同正整数”。

被分解的数一定是 $n$ 的约数，先把约数数组 $O(\sqrt{n})$ 搞出来。

接着从小到大枚举约数，dfs(tn,tk,tp) 表示剩余的数是 $\mathrm{tn}$，还需要分解成 $\mathrm{tk}$ 个数，当前已经在约数表中使用了前 $\mathrm{tp}$ 个数。剪枝是如果可选的最小的 $\mathrm{tk}$ 个数都超过 $\mathrm{tn}$ 就剪掉。

综合深搜技巧

骑士精神

不超过 $15$ 层，还是有迭代加深的道理的。

另外使用一个简单的乐观估价函数进行剪枝。

另外既然已经有乐观估价函数了，也可以 A*。

（类似送礼物的）背包问题

背包，物品数 $\le 40$，体积 $\le 10^9$。

$40$ 这个数字太敏感了，马上 Meet in the Middle。

集合划分

“相等”的限制条件让我们想到，枚举两个集合 $A,B$，若 $A\cup B=\varnothing$ 且 $\sum A=\sum B$，则 $A,B$ 为一组合法划分方案。

由于 $A\cup B=\varnothing$，因此上面的方法比较冗余——会产生大量的重复集合。

我们有更好的避免重复的方案：令 $C$ 是前 $\frac{n}{2}$ 个数组成的集合的划分方案（决定每个数在 $A$ 中、在 $B$ 中、都不在）， $D$ 是后 $\frac{n}{2}$ 个数组成的集合的划分方案，这样 $A\cup B=\varnothing$ 就自然成立了。$C,D$ 各有 $3^{\frac{n}{2}}$ 种。

并且，设一种划分方案的权值是 $\sum A-\sum B$，那么两种权值互为相反数的方案合起来可以构成一种合法方案。

但是注意！题目求的不是合法的划分方式数量，而且合法的能被划分的集合数量；也就是 $A\cup B$ 的数量。因此，我们还要记录 $C,D$ 中 $A\cup B$ 的值，设为属性 $s$。下面我们的任务就是，对右半的所有 $(w,s_r)$ 对，找出左半中所有的 $(-w,s_l)$ 对，并标记 $\mathrm{visited}[s_l \cup s_r]$。

我们可以想到一个简单的做法：把左半按 $w$ 排序，接着对于右半里的每一种划分，二分找出左半中所有的 $(-w,s_l)$ 对，一一标记即可。还有一个小优化，左右半都可以排序后 unique 一下，即 $w$ 和 $s$ 都相等的对，只保留一个。

这样做的复杂度怎么分析呢？对于每一个 $s_r$，它的所有不同的 $w$ 的总扫描长度（即扫描左半数组的长度）不会超过 $3^{\frac{n}{2}}$，也就是最多把左半数组扫完；二分查找复杂度 $O(\log {3^{\frac{n}{2}}})$，因此总计算量大概是 $O(2^{\frac{n}{2}}\times 3^{\frac{n}{2}}+3^{\frac{n}{2}}\times \log 3^{\frac{n}{2}})\approx O(6^{\frac{n}{2}})\approx 6\times 10^{7}$。

当然还有一个不需要二分查找的方法。把右半以 $s$ 为第一关键字、$w$ 为第二关键字排序，再按 $s$ 分成小块，每个小块内 $w$ 是单调的，这样就可以在左半用双指针单调移动，去除掉这个 $\log$。当然，扫描的复杂度可能也不小，因此这个优化可能差异不大。

总之，当 $n$ 比较小，你的算法没有很好地利用限制（“相等、不等、不交”）时，可以考虑 Meet in the Middle，从而更好地利用限制。

$n$ 皇后

用二进制优化哪些地方可选即可加快速度。

广搜

八数码

有明确的目标局面，可以使用双向广搜。

有简单的估价函数，可以使用 A*。也可以写 IDA*。

我原先写的 fake A* 不知道怎么过去的。

华容道

考虑搜索的状态是 $(s_x,s_y,b_x,b_y)$，分别表示目标棋子的位置和空白的位置。

空白的位置这个状态很浪费啊——空白只有在目标棋子的四连块处，目标棋子才能移动。

因此移动可以分为两类：

1. 目标棋子的移动——与目标棋子的起点和终点有关
2. 空白格的移动，即非目标棋子的移动——与空白格的位置、目标棋子的位置和空白格在目标棋子的方向有关。这种移动的目的是，把空白格移到目标棋子四连块的某一位置，从而使目标棋子移动。

这两类的变量不太一样，我们考虑分开处理。

由于第二类与输入关系较小，因此先预处理第二类移动情况。

设 $g[s_x][s_y][b_x][b_y][d]$ 表示把 $(b_x,b_y)$ 处的空白格移动到 $(s_x,s_y)$ 处的目标棋子的 $d$ 方向的最短距离，移动的过程中目标棋子不能动。在计算 $g$ 的过程中，我们只需要把目标棋子临时标记为不可动，状态只记空白格子的位置即可。

预处理了第二类的移动情况，实际上总的移动就变成了：空白格移动到目标棋子四连块——目标棋子移动——空白格移动——目标棋子移动——空白格移动……

不妨枚举最开始时空白格在目标棋子的哪一个方向，再把状态记为 $(s_x,s_y,d)$，表示目标棋子的位置和空白格的方向。这样……就是一个图了！图上的边有两类——当然是空白格移动（边权根据 $g$ 可得）和目标棋子移动（边权为 $1$）啦。

最后就是一个图上最短路问题了，点数 $4n^2=3600$，边数上界 $4n^2+3\times 4n^2=13n^2=11700$，用 SPFA 就可以满足需要。

指数计算

数组里初始时只有 $1$，每次可以从数组中取出两个（可以相同的）数，把它们的和或差加入数组（但是要求差必须为正），求最少需要操作多少次才能得到 $n$。

最少需要操作多少次？直接 IDA* 解决吧。乐观估价函数设为 $\log (n-x)$，其中 $x$ 是数组中最大的数。

还有一个玄学的搜索顺序优化，优先选大的进行扩展。

ABCDEF

这个式子很奇怪，进行一些移项后两边每一边都是三个数。这样就可以 Meet in the Middle 了。说实话这道题时间限制很危险，似乎要用哈希表才能过得去。

测试 1

帽子谜题

奇妙的“数学”题。

考虑实际上有多少种颜色的帽子，设这个数为 $x$。

那么戴着独特帽子（只有他一人戴着这种颜色的帽子）的人的 $a_i$ 就是 $x-1$，戴着不独特帽子的人的 $a_i$ 就是 $x$。

因此 $a_i$ 最大值和最小值的差不大于 $1$，并且最大值不大于 $n-1$。

下面分两种情况讨论。

一是所有人帽子颜色不同，那么 $\forall 1\le i\le n,a_i=n-1$。特判掉就好了。

二是所有人帽子颜色不全相同，这样必定有人戴着非独特的帽子。这时 $a_i$ 的最大值就是 $x$，最小值就是 $x-1$。

设有 $p$ 人的帽子颜色独特，有 $q$ 人的帽子颜色不独特，那么 $p+q=n$；并且恰有 $p$ 种独特的颜色。再设有 $r$ 种不独特的颜色，那么 $p+r=x$。

由假设“所有人帽子颜色不全相同”，则 $r>0$。又由“不独特”至少有 $2$ 人，因此 $q\ge 2r$。

这两个不等式整理一下就可以得出“合法”的条件了。

旅途

一道有意思的搜索题。

对于没有补给的情况，任意点都不会访问两次，因此只要建图跑最短路即可。

对于有补给的情况，就需要搜索了。

我用的是分阶段搜索。每领到一个补给，就进入一个新的阶段；同一阶段任意点都不会访问两次，搜过去即可。

标程的方法更为巧妙。如果经过一个点，使得生命值和经过的泥潭数都没有发生变化，那么一定是在闲逛！因此我们可以把 $(x,y,w,\mathrm{ans})$ 作为状态（$w$ 是生命值），这样就可以避免闲逛了。

但是这样似乎还不能加 visited？比如这一组数据

1
2
3
4
5
6

3 5 5
SMMM.
M###C
MM...
M####
ME###

好像就不太行的样子……

魔术

挺不错的计数题。

暴力方法当然是直接搜。

优化过的暴力就是从“独特”的字符开始搜，尽量减少不可能状态。

看这个数据范围，似乎只要 Meet in the Middle 就可以过呢。

可是……Meet in the Middle 如何快速合并呢？

要求不能重复……要是直接记录，状态空间过大，复杂度无法承受啊。

那怎么办呢？使用封印的秘法：容斥原理！

容斥原理复 (yu) 习 (xi)

容斥原理是一个很迷的东西，可以处理各种东西。

容斥原理：有一个全集 $U$，并且有若干个对 $U$ 中元素定义的谓词（bool 函数）$p_1,p_2,\cdots,p_n$，设满足谓词 $p_i$ 的元素集合为 $P_i$。设 $A_t$ 为恰好满足 $t$ 个谓词的元素的集合，如 $A_0$ 为 $\overline{P_1 \cup P_2 \cup \cdots P_n}$。现在想要求一个值 $W=w_0\vert A_0 \vert + w_1 \vert A_1 \vert+\cdots+w_n \vert A_n \vert$，其中 $w_0,w_1,\cdots,w_n$ 是任意给定的系数。也就是，每个元素对最终答案的贡献只与它满足的谓词个数有关，那么就可以使用容斥原理进行转化。

容斥原理是把“$\vert A_0\vert,\vert A_1\vert,\cdots,\vert A_n\vert$”这些不易求的量（可能需要枚举所有元素才能计算）转化为求另一些量。对于谓词的集合 $S$，设 $f(S)$ 为“满足集合 $S$ 中所有谓词的元素个数”（也就是“至少能满足 $S$ 中所有谓词的元素个数”），那么我们只需要对所有 $S$ 求出 $f(S)$，再把 $f(S)$ 赋予适当的“容斥系数”$s_j$，就能计算出 $W$ 了。注意这里的容斥系数 $s_j$ 仅与 $\vert S\vert$ 有关，也就是 $s_j$ 是 $\vert S\vert$ 的函数；谓词集合对答案的贡献也只与它的大小（所含的谓词的个数）有关。

总结一下，容斥原理转化是将求“恰满足 $t$ 个谓词的元素个数”转化为“对于每一个谓词的集合，计算至少满足这个集合中所有谓词的元素个数”，从“枚举元素，数满足的所有谓词个数”变成了“枚举谓词的集合，数满足该集合中所有谓词的元素个数”。

如何求“容斥系数”呢？“容斥系数”一定存在么？

假设任选的某个元素 $x$ 恰满足 $t$ 个谓词，那么这个元素对 $W$ 的贡献应该是 $w_t$。

下面我们从“容斥”角度考虑它对答案的贡献。如果用容斥原理计算答案，那么要考虑“它满足哪些谓词的集合中所有的谓词”——考虑这 $t$ 个谓词的集合 $B$，那么上面引号中条件的充要条件就是“这个谓词的集合是 $B$ 的子集”。因此只有 $B$ 的子集中才会出现 $x$ 的贡献。

也就是说，$x$ 只要想要对答案作出贡献，就必须作为某个“满足某个谓词集合中所有谓词的元素”，而这些谓词集合都是 $B$ 的子集；因此只需要对于 $B$ 的所有子集 $C$，计算出“把 $x$ 作为满足 $C$ 中所有谓词的元素”时作出的贡献，再把这个贡献求和，就能得到“容斥法计算出的 $x$ 对答案的贡献”。

考虑 $B$ 的一个 $j$ 元子集 $C$，那么 $x$“作为满足 $C$ 中所有谓词的元素”时对答案的贡献就等于容斥系数 $s_j$。

$B$ 一共有 $\mathrm{C}^{j}_{t}$ 个 $j$ 元子集，因此 $x$ 的总贡献就是 $s_0 \mathrm{C}^0_t+s_1\mathrm{C}^1_t+s_2\mathrm{C}^2_t+\cdots+s_t \mathrm{C}^t_t$。这个值应该与定义法算出来的 $w_t$ 相等，也就是 $s_0 \mathrm{C}^0_t+s_1\mathrm{C}^1_t+s_2\mathrm{C}^2_t+\cdots+s_t \mathrm{C}^t_t=w_t$。

上述方程涵盖了所有“满足 $t$ 个谓词的情况”。要涵盖所有元素的情况，也就是涵盖满足 $0,1,2,\cdots,n$ 个谓词的情况，我们就需要列 $t=0,1,\cdots,n$ 时的方程，并把这些方程联立起来求一组解。如果能求出解，那么“容斥系数”存在，并且我们也就求出了“容斥系数”。

这些方程是：

\begin{align}\begin{cases}s_0 \mathrm{C}^0_0&=w_0 \\ s_0 \mathrm{C}^0_1+s_1 \mathrm{C}^1_1&=w_1\\ s_0\mathrm{C}^0_2+s_1 \mathrm{C}^1_2+s_2 \mathrm{C}^2_2&=w_2\\ \vdots &= \vdots \\ s_0\mathrm{C}^0_n+s_1 \mathrm{C}^1_n+s_2 \mathrm{C}^2_2+\cdots+s_n\mathrm{C}^n_n&=w_n \end{cases}\end{align}

可以看到，一共有 $n+1$ 个未知数（$s_0,s_1,\cdots,s_n$）和 $n+1$ 个方程，而且未知数的系数矩阵是下三角矩阵，下三角矩阵的下三角部分全都非零（因为都是组合数嘛），因此是一定有唯一解的。

具体地说，$s_0=w_0$，$s_j=\frac{w_j-s_0\mathrm{C}^0_j-s_1\mathrm{C}^1_j-\cdots-s_{j-1}\mathrm{C}^{j-1}_j}{\mathrm{C}^{j}_{j}}=w_j-s_0\mathrm{C}^0_j-s_1\mathrm{C}^1_j-\cdots-s_{j-1}\mathrm{C}^{j-1}_j$，直接递推就可以 $O(n^2)$ 求出所有容斥系数。

如果想要更快呢？

我们整理一下式子，把式子写成求和号的形式：

$s_j=w_j-\sum^{j-1}_{k=0}s_k\mathrm{C}^k_j$

把组合数拆开：

$s_j=w_j-\sum^{j-1}_{k=0}s_k\frac{j!}{k!(j-k)!}$

像数列一样把变量的形式调整得更相似：

$\frac{s_j}{j!}=\frac{w_j}{j!}-\sum^{j-1}_{k=0}\frac{1}{(j-k)!}\times \frac{s_k}{k!}$

令 $T_j=\frac{s_j}{j!}$，$Q_{j-k}=\frac{1}{(j-k)!}$，$L_j=\frac{w_j}{j!}$（变量名都是乱选的，不要打我）（这些都是可以 $O(n)$ 转化为答案或 $O(n)$ 计算出来的），那么：

$T_j=L_j-\sum_{k=0}^{j-1}T_k Q_{j-k}$

这是一个典型的卷积型式子，已经可以用分治 FFT 在 $O(n\log n\log n)$ 的时间内解决了。

还可以做得更好吗？

这个式子里面有卷积以外的求和，很讨厌。不妨把式子重新移项整理成更整齐的形式：

$\sum_{k=0}^{j-1}T_kQ_{j-k}+T_j=L_j$

由于 $Q_0=1$，因此左边可以整理成很漂亮的形式：

$\sum_{k=0}^{j}T_kQ_{j-k}=L_j$

标准卷积出现了！下面我们把它改成多项式。

设 $F(x)=\sum_{i=0}^{\infty} T_ix^i$，$G(x)=\sum_{i=0}^{\infty} Q_ix^i$，$H(x)=\sum^{\infty}_{i=0}L_ix^i$，那么

$F\times G=H$

也就是

$F=H\times G^{-1}$

于是就可以用多项式求逆 $O(n \log n)$ 解决了！

另外注意一个细节，$G(x)=\sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x$，因此 $G^{-1}$（是逆元，不是反函数）就是 $e^{-x}$！那还求什么逆呢？$e^{-x}=\sum^\infty_{i=0}\frac{(-x)^i}{i!}=\sum^\infty_{i=0}(-1)^i\frac{x^i}{i!}$。

下面我们研究一下经典的容斥。

$w_0=1,w_1=w_2=\cdots=w_n=0$ 当属最经典的容斥——求不满足任何一个谓词的元素个数。此时 $H(x)=1$，$F(x)=e^{-x}$，也就是 $T_i=\frac{(-1)^i}{i!}$，得到 $s_i=(-1)^i$。这和我们用经典方法得到的结果一致，也就是加上偶数的、减去奇数的。

那如果是 $w_0=w_1=\cdots=w_{k-1}=w_{k+1}=\cdots=w_n=0,w_k=1$——求恰好满足 $k$ 个谓词的元素个数呢？此时 $H(x)=\frac{x^k}{k!}$，$F(x)=\frac{x^k}{k!}e^{-x}=\sum^{\infty}_{i=0}(-1)^i\frac{x^{i+k}}{k!i!}=\sum_{i=k}^{\infty}(-1)^{i-k}\frac{x^{i}}{k!(i-k)!}$，$T_0=T_1=\cdots=T_{k-1}=0$，$T_i=\frac{(-1)^{i-k}}{(i-k)!}$，$s_i=i!T_i=(-1)^{i-k}\frac{i!}{k!(i-k)!}=(-1)^{i-k}\mathrm{C}^k_i$。

阅读上面这段推导过程的时候一定要明确 $T,Q,L,F,G,H$ 各自的定义！或者，如果撇开 $T,Q,L$，$F,G,H$ 分别可以看成是 $s,1,w$ 的 EGF（注意不是 OGF！）。

如果是 $w_0=w_1=\cdots=w_{k-1}=0,w_k=w_{k+1}=\cdots=w_n=1$——求至少满足 $k$ 个谓词的元素个数呢？如果觉得用多项式直接做有困难，可以尝试用一下乘法分配律（从组合意义上说是加法原理）——把“至少 $k$ 个”拆成“恰好 $j(k\le j\le n)$ 个”的和。这样 $s_t=\sum _{j=k}^{t}(-1)^{t-j}\mathrm{C}_{t}^{j}$。这个和式有点像朱世杰恒等式的形式，可以试着用 $\mathrm{C}^r_n=\mathrm{C}^{r-1}_{n-1}+\mathrm{C}^{r}_{n-1}$ 变形，变形的结果是 $s_t=(-1)^{t-k}\mathrm{C}^{k-1}_{t-1}$。

当然，对于大多数非经典的容斥问题，可以先在纸上画表找规律，说不定就能求出来了呢。实在不行还可以使用暴力求系数或多项式算法。

用容斥原理解本题

回到本题，我们想要处理的就是“如何选出交集为空的前后状态”。

设前半段有 $n$ 个字符。如果我们以“前半段”为思考主体，对于某一个确定的前半段选择方案，取 $n$ 个谓词，其中第 $i$ 个谓词为“后半段是否选到了前半段的第 $i$ 个字符”。我们想要的是“不满足任意谓词的后半段个数”，那么根据上面经典容斥的第一个模型，容斥系数是 $(-1)^t$。也就是，对于字符的 $t$ 元集合 $S$，“至少取到 $S$ 中所有字符的每一个后半段”要对答案有 $(-1)^t$ 的贡献。

于是，我们可以枚举前半段选择方案，再枚举它所选的字符集合的子集 $S$，求出“至少取到 $S$ 中所有字符的后半段”的个数（设这个数是 $u$），再给答案累加上 $(-1)^{\vert S \vert}u$。

如何求出“至少取到 $S$ 中所有字符的后半段”的个数呢？这个条件的充要条件就是“$S$ 是这个后半段所选字符集合的子集”，因此我们对于每一个后半段，枚举它的子集，在子集处累加 $1$ 即可。

另外注意，由于前半段和后半段要能连起来，也就是断点处的字符必须是一样的，因此我们要先枚举断点，然后由断点向两边分别枚举后半段和前半段，累加计算答案。

总结一下，本题的解题框架是：先枚举断点；从断点往右找后半段，在找出的每一个后半段的子集处标记；从断点往左找前半段，枚举找到的前半段的每一个子集，累加答案。

线性数据结构

链表

哈希表 (Hana’s Table!)

对于一个字符串或大整数，可以把它模 $\mathrm{mod}$（大质数）的值作为“特征值”，把它模 $p$（小质数）的值作为“哈希索引值”；每次按照索引值查找，如果找到特征值，那么就认为这个对象存在。

栈, 队列

蚯蚓

发现“单调”的结论很重要，当然也可以直接感性理解、略去证明。

单调栈, 单调队列

什么是单调性思想？

简单地说，就是“如果一个 OIer 比你小，还比你强，那你就打不过他了”！

稍形式化地说，这类问题中的元素有时效性（转移的能力）和价值（值的优劣性），如果一个元素的转移能力和价值都超过了另一个，那么它就总可以替代另一个，于是另一个就不必被保存。

单调性数据结构主要有，单调队列、单调栈、二分单调栈、单调性 set 等。

Print Article

状态转移方程 $f[i]=\min(f[j]+(s[i]-s[j])^2)+M$，其中 $s$ 数组单调递增。

观察一下——这个东西具有决策单调性！为什么？

考虑设 $w_j(x)=(x-s[j])^2+f[j]$，那么 $f[i]=\min(w_j(s[i]))+M$。$w_j$ 是二次函数，而且所有 $w_j$ 都可以通过互相平移得到。

考虑两个这样的二次函数（不重合），它们的差是一个一次函数——一次函数是单调的，因此一旦一个函数变得优于（从劣于变到优于）另一个，它就永远优于另一个了。而且由于这些二次函数的对称轴单调右移，因此后面的状态最终都会比前面的状态优。

或者我们也可以拆式子。$w_j(x)=(x-s[j])^2+f[j]=x^2-2s[j]x+s^2[j]+f[j]$。可以发现这是一个以 $-2s[j]$ 为斜率的一次函数，斜率是随时间（计算顺序）单调递减的，后面总比前面优。因此可以使用单调队列维护当前直线（“上/下凸壳”），发现队头变劣就弹掉；加入新直线时，如果发现新直线与队尾直线的交点小于队尾直线与队尾前一条直线的交点，即新直线的生效点在队尾直线的生效点以前，新直线完全覆盖了队尾直线，就把队尾直线弹掉。

注意这样的斜率 dp 与“函数平移”型决策单调性 dp 的区别——这里的入队比的是生效点，就像用 set 的普通斜率优化 dp 比较“作用范围元组”一样；而很多“函数平移”型 dp 只需要比较“在当前点的大小”。弹队头和入队时弹队尾都是单调队列正确性的保证。

关于决策单调性

简单的决策单调性，斜率如果随时间单调变化，可以用单调队列或单调栈。

困难的决策单调性，没有明显的斜率，可以使用二分单调队列或二分单调栈。

困难的斜率优化，斜率不按时间单调变化，可以用 set 维护。

极为困难的决策单调性！既没有明显的斜率，函数又不便计算的……

考虑用 CDQ 分治（整体二分）！

单调队列优化多重背包

具有决策过期性质，可以用单调队列维护。

Little Bird

每个状态具有位置、高度两个属性，这两个属性都具有单调特点。

等等，高度没有范围，劳累值有范围——考虑反转值域，把位置（树的序号）和劳累值作为定义域，高度作为值域。这样还有天然的好处——类似 LIS 的福利，每次转移只差 $1$！或者说这题就和 LIS 非常相像吧。

但是这个“双单调”怎么办呢？

我们可以用单调数组（类似 LIS）套单调队列解决。

单调数组中每一个数就对应一个单调队列，单调队列维护位置属性，单调数组维护高度属性。

Blocks

求最长的均值不小于 $k$ 的子段。每个数减去 $k$ 后变为求最长的和非负的子段。

考虑枚举区间右端点，也就是对每一个 $r$，要在 $O(1)$ 时间求出一个最小的 $l$，使得 $S_l\le S_r$。

考虑单调覆盖性质。一个状态的转移能力由 $S$ 决定，$S$ 越小，转移能力越强；价值由位置决定，位置越靠左，价值越大。如果一个状态的 $S$ 比另一个大，位置还在另一个的右边，那就会被“另一个”覆盖。

因此可以维护一个不被覆盖的反链——$S$ 与位置反向变化的东西，因为询问的高度不单调，因此每次在反链中二分寻找即可。

二分？这怎么 $O(1)$？

其实右端点也有单调覆盖性质！右端点的 $S$ 越大，转移能力越强；位置越靠右，价值越大。因此右端点也在一个反链里！

这样我们可以把左边的反链和右边的反链都做出来，这样枚举右端点的时候 $S$ 就是单调变化的了！既然是单调变化的，那么左端点那边的反链就可以单调删除元素，转移能力得以真正体现！

你要问我“反链”用什么维护？当然是单调栈啦！

综上，当前后状态都按照转移能力的单调顺序（前状态的转移能力越来越强，后状态的转移能力越来越弱）给出时，我们便可以用单调队列或单调栈 $O(1)$ 解决；如果没有完全按这个顺序给出，但是具有单调的（偏序）覆盖性质的话……我们就取反链，反链就是单调的啦！

另外……反链总是包含了”无敌状态“——转移能力最强的零状态。

树形数据结构

并查集

简单题

$n$ 点 $m$ 边无向图，一旦一个点的度为 $1$，这条边就会自动消失。求至少要人工删除多少条边，使得这个图中没有边。

如果一个图有环，一定不能变成无边状态。因此图一定要删到无环的状态。

考虑一棵树，我们都知道树有 Prufer 序列对吧？树的 Prufer 序列其实就是一个类似上面的过程，因此树一定可以变成无边状态。

综上，我们只需要把每一个连通块都变成树即可。那么要删的边数就是（每个连通块） $m-(n-1)$。

例题

给定一个无边的 $n$ 点图，在线维护这个图，每次操作连接两个点或询问这两个点连通的最早时刻。

可以用“边带权”的并查集解决，边权就是操作的时刻。合并时按秩合并即可保留树的结构，ufind 的时候顺手计算一下边权的最大值即可。

题目可以改成“给定图上两点，询问它们之间所有路径上‘边权最大值’的最小值”。按边权从小到大加边即可。

类银河英雄传说 (Cube Stacking)

每次有 merge 和查询到根距离两种操作，merge 时指定方向。

不能按秩合并，那就路径压缩。边权记为到父亲距离。

黑白点（[HEOI2016/TJOI2016]树）

有一棵树，初始时只有根节点是黑的，每次操作染黑一个点或询问一个点的最近黑色祖先。

染黑一个点就相当于把这个点的子树与它的父亲断开，查询最近黑色祖先就是查所在子树根节点。

如果正着做就是断开，不好做；于是把操作离线，倒序处理，就变成了连接（merge），就可以用并查集了。

如果强制在线怎么办？

用类似树链剖分的方法——这回不需要维护树上两点路径，因此直接按 dfs 序即可——建立线段树，这回有区间上推（如果小于 $x$ 就改成 $x$）的修改操作，打上标记即可。

ST 表与倍增

ST 表求 LCA

对每个节点，每次访问到就在数组中记录一次（这叫做欧拉序）。比如 $1$ 有 $2,3,4$ 三个孩子， $2$ 有 $5,6$ 两个孩子，那么这棵树的欧拉序就是 $1,2,5,2,6,2,1,3,1,4,1$。考虑欧拉序的记录方法，来到一个节点的时候记录一次，每遍历完一个子节点记录一次——因此长度为 $n+m=2n-1$。

现在把欧拉序中记录的每个节点的编号改成记录每个节点的深度，接着再记录一下每个节点在欧拉序上的开始位置和结束位置（$\mathrm{op,ed}$？），这样对两个点，只要查它们 $\mathrm{op,ed}$ 之间的最小深度就可以了。

这个深度欧拉序有什么特征么？相邻两个点的深度只会变化 $1$，也就是数列中每两个数的大小要么差 $1$，要么差 $-1$！这就是——

$\pm 1$ RMQ

我们怎么求 $\pm 1$ RMQ 呢？这里有一种玄学的分块方法，可以做到 $O(n)$ 预处理、$O(1)$ 查询！

考虑把整个数列分成大小为 $\lfloor \frac{\log n}{2} \rfloor$ 的块（取整符号下略），那么总共就有 $\frac{2n}{\log n}$ 块。我们把每一块的最小值都求出来。

现在把每一块看作一个整体，组成一个“块的数列”——长为 $\frac{2n}{\log n}$。对这个数列作 RMQ，使用 ST 表，复杂度为 $O(\frac{2n}{\log n}\times (\log (2n)-\log\log n))\approx O(n)$。

查询时怎么办呢？分块的思想是“整体使用预处理信息，局部暴力”。起点和终点之间部分的最小值可以直接用“块的数列”的信息得到，但是起点和终点所在块的最小值呢？这个要是暴力，查询可就不是 $O(1)$ 的了！

这时候就要用到性质了。首先，如果一个区间的差分数列是确定的，那么这个区间的区间最值的位置也就是确定的。接着，由于是 $\pm 1$ RMQ，因此每一块内部的差分数列也就只有 $2^{\frac{\log n}{2}}=\sqrt{n}$ 种，暴力枚举这所有的块内差分可能性，对每一种可能性，都算出它所有子段（有 $\mathrm{C}^{2}_{\frac{\log n}{2}}\approx \log n\log n$ 种）的最值位置，这个过程的总复杂度是 $O(\sqrt{n}\log n\log n)<O(n)$。查询时就直接根据当前块的差分数列种类，查看相应种类、相应区间的最值表，就可以做到 $O(1)$ 查询了！

看起来这样树上 LCA 就可以很快地完成了！但实际上——

笛卡尔树

假如我说树上 LCA 可以转为 $\pm 1$ RMQ，那么你是相信的。

假如我说一般的 RMQ 可以转为 LCA，你信么？

不管你信不信，这确实是可以 $O(n)$ 做到的。

笛卡尔树是一棵满足堆性质和 BST 性质的二叉树：

父节点的值大于 / 小于子节点的值，也就是值满足堆性质；

左节点的下标小于父节点，右节点的下标大于父节点，也就是下标满足 BST 性质。

是不是和 Treap 有点像？当然，它们的作用还是有很大差别的。

事实上，笛卡尔树上两点的 LCA 正是这两点形成区间的 RMQ！（稍加模拟，我也不想证明。）

那么现在的问题就是怎么建立笛卡尔树了。

考虑从左到右一个一个地把数加入到笛卡尔树中。最后加入的数一定在树的右儿子-右儿子-右儿子这一条链上，也就是一定是在最右边。我们选这样一条从根节点一直往右走的路径作为树的主链，把主链中的点插入一个栈中，把左儿子“挂”在主链上。那么最后加入的树一定要插入栈中。

根据堆性质，如果这个数比栈中所有数都大 / 小，那么我们就可以把这个点直接放在栈顶。否则，假如这个数只比栈中的前 $l$ 个数大 / 小，那么我们就把后面的树整体拿出来，作为这个点的子节点。实际操作时不断弹栈，直到栈为空或栈顶节点满足堆性质，再把刚才最后一个弹出的节点作为这个点的左儿子，最后入栈即可。

可以看出，上述建树过程是 $O(n)$ 的。因此只要我们先建出笛卡尔树，再根据笛卡尔树的欧拉序做好 $\pm1$ RMQ 的预处理，我们就可以做到 $O(n)-O(1)$ RMQ 了！

当然读入一个数是 $O(\log_{10} x)$ 的，所以实际上作用也不是很大……

但是可以过由乃救爷爷这一题。

倍增与 Floyd

$n$ 点 $m$ 边有向图，边有边权。问从 $1$ 号点开始，最少需要走多少条边才能使得经过的边的边权之和不小于 $s$。

首先可以想到动态规划，$f[i][j][k]$ 表示从 $i$ 走 $k$ 条边、来到点 $j$ 的最大边权和，$f[i][j][k]=\max(f[i][t][k-1]+w[t,j])$。

这个方程看上去不是很均衡，左边是 $k-1$，右边是 $1$……

考虑用倍增优化：设 $f[i][j][k]$ 是从 $i$ 走 $2^k$ 条边、来到点 $j$ 的最大边权和，$f[i][j][k]=\max(f[i][t][k-1]+f[t][j][k-1])$。这样我们就能在 $O(n^3\log k)$ 的时间完成 dp 方程的计算。

下面考虑如何计算答案。

考虑倍增求答案。从大到小枚举 $k$，如果所有 $f[i][j][k]$ 都小于 $s$，就把答案加上 $2^k$，同时记录一个 $g[i]$，表示走了 $\mathrm{ans}$ 步，到达点 $i$ 后的最大边权和，$\mathrm{ans}[i]=\max(\mathrm{ans[j]+f[j][i][k]})$，又是一个 $O(n^2 \log k)$，就可以完成了。最后答案别忘了额外加 $1$，道理和倍增 LCA 相同。

ST 表与并查集

[SCOI2016]萌萌哒：求满足 $m$ 个形如”$[l_1,r_1]$ 到 $[l_2,r_2]$ 两个区间内的数字对应相等“的限制条件的没有前导零的 $n$ 位数的数量，模 $10^9+7$。

考虑暴力怎么写。用并查集维护“相等”的条件，每次暴力连边，最后统计连通块的数量，有一个（包含最高位的那一个）连通块有 $9$ 种选择，其余连通块都有 $10$ 种选择，直接计算即可。

这个并查集 merge 操作显然太多了，怎么办呢？我们需要一种高效的区间 merge 的方法。

我们能不能给区间打个标记，标记意味着这个区间整体和另一个区间 merge 了呢？

这样我们就要考虑把区间拆成若干个小区间——ST 表就可以，因为重叠也没关系。

每次合并的时候就把 $[l_1,l_1+2^k-1]$ 与 $[l_2,l_2+2^k-1]$ 合并，相应地把第二个区间合并。

再考虑如何得到连通块的个数。其实很简单，把 $\mathrm{LC}(x)$ 与 $\mathrm{LC}(\mathrm{ufind}(x))$ 合并、$\mathrm{RC}(x)$ 与 $\mathrm{RC}(\mathrm{ufind}(x))$ 合并即可，其中 $\mathrm{ufind}(x)$ 指的是 $x$ 在并查集上的根。

线段树

诡异的线段树

线段树与区间色数

[POI2015] KIN：选取一个连续的区间，使得区间中只出现一次的数的种类最多。

考虑枚举区间右端点，维护右端点在此位置时不同左端点的答案变化情况，并直接取 $\max$ 即可。

怎么维护呢？考虑新加入的数 $x$ 对答案的影响。设 $x$ 上一次、上上次出现的位置分别为 $l_1,l_2$，那么在区间 $(l_2,l_1]$ 中，$x$ 从只出现一次变为了出现多次，答案减一；在区间 $(l_1,\mathrm{cur}]$ 中，$x$ 从不出现变为了只出现一次，答案加一。因此发生答案改变的左端点是一个区间，可以用线段树的区间加操作实现；求 $\max$ 也可以用线段树解决。因此，这题只需要用线段树就可以了！

于是，我们找到了用线段树维护（持续维护、可以维护所有区间）区间色数的方法。此外，某些区间色数问题还可以用双指针解决——求最短的至少包含 $k$ 种颜色的区间，若枚举左端点，左端点右移，则右端点单调右移。树上的色数问题可以用 $\mathrm{dfs}$ 序或树链剖分转为序列区间色数问题。

线段树与区间上下推

这是一道 IOI 原题。

给定一个初始全 $0$ 序列，有两种操作：

1. 对某区间内的所有数 $x$，令 $x=\max(t,x)$（$t$ 是操作参数）
2. 对某区间内的所有数 $x$，令 $x=\min(t,x)$

求最后的序列。

这道题与“萌萌哒”类似，如果每次区间操作都暴力地对区间内每一个数都进行调整，那么复杂度将无法承受。我们需要选择一种数据结构，直接对“区间”进行操作。

“萌萌哒”这道题中，操作之间互不影响，而且操作区间可以重叠，因此可以直接使用 st 表（若操作区间不可重叠，同样可使用 st 表，但操作区间要被二进制拆分成为 $O(\log l)$ 个）。但是在这道题中，不同的操作前后会有影响，因此我们可以使用线段树。

线段树的每一个点维护“已经对这个区间进行、但还没有对这个区间的孩子应用 (apply) 的限制”——如果我们把我们的数想象成一排金属球，那么 1 操作可以想象成用一块钢板从下往上推区间内的球，一直推到高度 $t$，使之不低于 $t$；2 操作可以想象成用一块钢板从上往下压，一直压到高度 $t$。于是“每个区间的限制”有两种，一种是向下压的板到达的最小高度，一种是向上推的板到达的最大高度。初始时长度大于 $1$ 的区间都没有限制——向下压的板的最小高度（记为 $n$）为 $\infty$，向上推的板的最大高度（记为 $m$）为 $0$；可以认为初始时长度为 $1$ 的区间的 $n$ 和 $m$ 都是 $0$。

现在考虑对一个区间进行 1 操作。用一块自下而上的上推钢板推这个区间，会有什么变化呢？如果原来的下界钢板低于 $t$，当然会被推到 $t$ 位置，否则不变；上界同理。因此，这个操作对这个区间的变化是 $m=\max(m,t),n=\max(n,t)$。

再考虑 2 操作，类似地，$m=\min(m,t),n=\min(n,t)$。

由于有些操作之间会相互影响，因此如果有一个要应用到孩子、但不应用到父亲区间的操作，就必须先把标记下传。标记下传也就是把之前 lazy tag 延迟应用的操作应用到孩子上，也就是对孩子进行 $1\ m,\ 2\ n$ 这两个操作——这两个操作的顺序无关紧要，因为在维护父节点的两个标记的时候，已经保证了这两块钢板 $m\le n$，因此这两个操作之间不会相互影响。

输出的时候直接输出叶子节点的 $m$ 或 $n$ 即可。由于上述过程中，叶子节点的 $m,n$ 始终相同——夹着单个球的板总是紧密合在一起的，因此输出哪一个都可以。

动态开点线段树与线段树合并

对于权值线段树，如果要像普通线段树那样静态建树、开点，空间将是非常非常大的，完全——无法承受啊！

于是有了动态开点的操作。对于一个线段树节点，都像平衡树一样记录它的左子和右子，需要时再开点记录。可以用“引用”来优化实现。对于一个长度为 $n$ 的区间，动态开点线段树只需要 $2n$ 的空间就足够了。

动态开点线段树还有一个好处——可以快速合并两棵结构相同的线段树！所谓“结构相同”指的就是“维护的区间（长度）相同”，这样它们对区间的划分就是相同的。

合并的方法是，同时遍历这两棵线段树，如果两棵树当前节点都为空，那么合并后的树当前节点也为空；如果两棵树中只有一个当前节点为空，那么合并后的树直接使用另一棵树中的当前节点；如果两棵树当前位置上都有节点，那么递归合并；如果到了叶子节点，就把信息合并为一个节点，插入即可。

合并的复杂度是多少呢？每次递归就相当与删除了一个节点，因此复杂度不会超过删除所有节点的复杂度——也就相当与把所有曾经做过的插入操作重新做一遍嘛——当然这是一个上界。大多数时候，线段树合并还是非常高效的。

线段树合并与逆序对

[POI2011]ROT-Tree Rotations：给定一个 $n$ 个叶子的二叉树，每个非叶节点都有两个孩子，可以交换任意非叶节点的左右子树，求交换后树的叶子遍历序列（按先序 / 中序 / 后序中任意一种方式遍历树，把遇到的叶子的权值依次记录）的逆序对数的最小值。

我们首先可以注意到，交换某个非叶节点的左右子树，只影响这个非叶节点左右子树对应的两个子段之间的逆序对数量，不会影响两个子段之内以及其他位置的逆序对数量。因此，我们每次只需要比较两个子段之间的正序对和逆序对数，若逆序对数多则交换，否则不换即可。

如何统计两个序列之间的逆序对数量呢？我们当然可以用归并排序的方法统计，但是归并排序每次归并是 $O(n_1+n_2)$ 的，如果我们的树极度不均衡，在一条主链上，每个主链节点都外挂一个儿子的话……自然就被卡到接近 $O(n^2)$ 了吧。

怎么办呢？想一想求逆序对还有什么办法？当然是利用树状数组了——这里当然要“应景”地改为利用权值线段树。这样，我们的“归并”过程不久变成了线段树合并么？

在线段树合并的过程中，如何统计逆序对数量呢？考虑左半部分一个较大的数和右半部分一个较小的数，记他们在合并后的树中的 LCA 为 $t$，那么在合并前的两棵树中，它们分别在左半部分节点 $t$ 的右子树和右半部分节点 $t$ 的左子树中，反之亦然。因此这是一个一一对应关系，我们只需要维护线段树每一个节点的 size，合并的时候对应相乘相加就好了。

复杂度是比较优秀的，当然常数还是稍大……注意卡常以及用垃圾分类回收卡空间。

线段树灵活反转值域

还记得反转值域吗？哪个维度方便、哪个维度范围小，就把哪个维度作为定义域；把不方便、范围大的维度作为值域！

CF911G Mass Change Quries：给定一个长度为 $n$、值域为 $[1,100]$ 的序列，每次操作把特定区间中的所有 $x$ 改为 $y$（$x,y$ 都在值域内），求所有操作完成后的序列。

就像不能把 12 岁以下儿童放在副驾驶座上一样，看到 $x,y$ 这么小，你忍心把她们放在值域上吗？倒是 $n$ 比较大，可以放进值域里。

好了，我们决定照顾儿童，把 $x,y$ 作为定义域。对每个数值（$x$），建立一棵权值线段树，向线段树中插入这个数值所在的所有位置。比如说第 $1,3,4$ 个数是 $2$，就向 $2$ 的线段树中插入 $1,3,4$。

对于每一次修改操作，我们只需要把 $x$ 线段树中这个区间相应的节点“剪切”下来，“粘贴”到 $y$ 线段树中就可以了！

怎么“剪切”、“粘贴”呢？这又不是 Splay……

不是 Splay 就不能快速分裂合并了吗？用类似线段树合并的方法，遍历到需要剪切的区间的时候就把节点指针“递给”需要粘贴的线段树。

这就是一种很不错的做法了。

其实还有一种更暴力的做法，每个节点维护“这个区间的 $x$ 都变成了什么”，注意每一次都要暴力更新标记。记住“父节点的标记比子节点的标记时间要晚”。

线段树与区间覆盖

[NOI2016] 区间：给定 $n$ 个区间，要从中选出 $m$ 个区间，使得这 $m$ 个区间的交非空。定义一个区间的长度为右端点减左端点，定义一种选择方案的代价为所有被选区间长度的极差，求代价的最小值。

这里首先用一个贪心的“选择扩充”——在不影响答案的情况下，要尽量多选，使得一个原先不满足题意的方案变得满足题意。（另一种常用的贪心策略是“选择压缩”——在保持选择方案满足题意的情况下，尽量少选，使得答案变优。两种贪心思想要综合运用。）

怎么扩充呢？当然是“如果把区间按长度排序，最终方案所选的区间的长度是连续子段”咯——毕竟最长和最短区间之间的所有区间都可以贪心地选上嘛。

这样就可以枚举两个区间端点暴力了。再多想一想，这个枚举可以优化么？

观察到，最短区间长度增加时，最长区间长度不减——“单调移动”性质！这样就可以用双指针解决了。

还有一个问题！如何判定当前所选的这些区间是否满足题意？“快速判定”也是单调枚举算法的重要环节啊。

当然是要用到线段树。对每个被选区间，在线段树相应的区间中每个点加 $1$，然后查询全值域的最大值，如果最大值不小于 $m$，那么符合题意——如果真的要选出 $m$ 个区间，我们就选“覆盖了这个点的所有区间中的任意 $m$ 个”就行了嘛！

还有一个小问题——区间端点数值太大，达到 $10^9$！哎呀这算什么问题呀，直接离散化就好了。

这样，我们就在 $O(n \log n)$ 的时间内解决了问题。

线段树优化 dp

CF834D The Bakery（此题洛谷无）：有 $n$ 个数字，要把它们分隔为 $k$ 个部分，统计每个部分的色数，再把这些色数全部加起来作为答案。问答案最大是多少。$n\le 35000,\ k\le 50$。

看到这个，当然考虑 dp 了。设 $f[i][j]$ 表示把 $[1,i]$ 分成 $j$ 个部分的最大答案，那么 $f[i][j]=\max(f[t][j-1]+\mathrm{color}[t+1...i])$。这样就可以 $O(n^2k)$ 暴力了。

考虑优化上面的 dp 式子。还记得上面的“线段树与区间色数”吗？线段树可以高效地维护所有区间的色数，这样我们就可以用线段树高效地维护上面 $f[t][j-1]+\mathrm{color}[t+1...i]$ 这个式子（实质是区间色数加一个与右端点无关的常数）了，维护后区间 $\max$ 即可。

扫描线

扫描线求矩形面积

每碰到一个矩形，就把矩形对应的区域加 $1$，查询所有最小值为 $1$ 的子区间长度即可。

扫描线维护区间信息

UVA1608 不无聊的序列 Non-boring sequences：如果一个序列的任意连续子段都存在只出现了一次的元素，就称这个序列是不无聊的。请判断给定的序列是否无聊。

这里又出现了“区间色数”之类的东西！完全可以用“线段树与区间色数”中的想法，维护区间“独特元素数”，右端点右移时维护线段树并查询区间最小值即可。

当然我们还有另外的解法。

考虑某个数 $x$ 在序列中的出现，设它的出现位置依次为 $y_1,y_2,\cdots ,y_k$，那么任意左端点在 $[1,y_i]$，右端点在 $[y_i,y_i+1)$ 范围内的区间都是有独特元素的。反之，对任意有独特元素的区间，都存在一个数 $x_0$，使得这个区间的两端点满足上述条件。因此这是一个“充要条件”。

我们考虑类似线性规划的方法，把区间的左右端点作为两个维度，区间化作点画在 $\mathbb{R}^2$ 上。那么一个“充要条件”就相当与把条件的区域用矩形覆盖，最后就检查是否所有区间都被覆盖即可。这就可以用扫描线处理了。

综上，对于“区间”、“限制条件”的问题，我们也可以用线性规划的方法，把限制条件和所求点标到 $\mathbb{R}^2$ 上，用扫描线维护。

树状数组

树状数组维护各种区间修改，重点是推式子、交换求和号——可以画图辅助理解。

此外树状数组还有单点修改、维护区间最值；充当平衡树等诡异功能，常数小，编码简单，值得一学(bei)。

Trie

Trie 的主要作用是处理位运算，特别是异或。

$\mathrm{mex}$

（全局）异或对 Trie 的改变，就是如果这一位为 $1$，那么这一层的所有左右儿子反转；如果这一位为 $0$，那么没有影响。

例题：给定一个长度为 $n$ 的自然数序列 $A$，每次操作全局异或一个数 或者 求 $\mathrm{mex}$。

由于异或具有结合律，因此把异或过的所有数维护到一个数，表示“之前所有异或操作的等效”，这样根据上面“全局异或对 Trie 的改变”一节，只需要根据这一影响，在每一位讨论是“尽量往左走”还是“尽量往右走”即可。

如果在走的过程中遇到了期望方向没有儿子的点，那么就已经找到了；如果走的时候发现期望方向是满的，那就要往非期望方向走。特别地，如果整棵树都是满的，那么就输出 $2$ 的一个幂。

51nod 1601 完全图的最小生成树计数

这里肯定要用贪心咯。

怎么求最小生成树？最小生成树是尽量取边权小的边构成生成树。边权？考虑贪心。

最高位是 $1$ 的边有没有必要选呢？假如我们不连任何最高位是 $1$ 的边，那么“最高位是 $0$ 的点集”和“最高位是 $1$ 的点集”之间就没有边了，它们之间不连通，这肯定不是最小生成树。因此这样的边必须连一条。能不能只连一条呢？只要上述两个点集自身都是树，那么连一条边就可以把这两棵树合并起来了。尽可能少地选边权大的边，就是尽可能多地选边权少的边，这是符合最小生成树的求法的。

因此我们的策略就是，把点按点权分成“最高位是 $0$ 的点集”和“最高位是 $1$ 的点集”，递归求解点集内部的生成树，再选择一条边权最小的“跨接边”就好了。

如何选“跨接边”呢？把这两个点集中的点放在同一棵 Trie 中，在分叉后尽量地往相同方向走，如果 $0,0$ 和 $1,1$ 都存在，那么就两种都试一试。

这么做，复杂度有保证么？

考虑每一个数，它会被分到 $\log v$ 个集合中，在每个集合中它最多会被遍历到一次，遍历一次的复杂度是 $\log v$，因此每一个数对复杂度的贡献是 $O(\log v\log v)$，总复杂度就是 $O(n\log v\log v)$，可以通过。

方案数怎么统计呢？方案数当然是所有跨接边的选择数之积了！只要在找跨接边最小值的时候顺便数一下方案数即可。

最后还有一个细节。如果最后遍历到了叶子节点，叶子节点不止一个数怎么办呢？

跨接边当然是可以乱选，这些“跨接边”的代价都是 $0$。但是方案数……

$n$ 个节点的有标号无根树数量是 $n^{n-2}$，乘上这个数就好了。

异或粽子

这道题……我确实有一个复杂度玄学但是跑得很快的分治做法。

正解是怎么做的呢？可持久化 Trie

当然先转化为前缀异或，这样就转化为了两两异或前 $k$ 大。

怎么办呢？还记得另一道题么？

有 $m$ 个有序序列，求这些序列合并起来后的前 $k$ 大。

只要用一个最大堆，插入每一个序列的最大候选值。然后每次取堆顶，再把堆顶所在的序列的下一个候选值放进堆，取 $k$ 次就好了。

如果我们枚举左端点，那么就能快速求出这个左端点异或的“后继”——次优解。于是就像上面这样建一个堆，每次取堆顶、插入候选即可。

这题其实主要考的还是“前 $k$ 大”的处理方法吧。

分治

核心思想：缩小问题规模。

求第 $k$ 大

有两个有序序列，如何在 $O(\log n)$ 的时间求出合并后的第 $k$ 大数？

想到“缩小问题规模”这个思想了吗？如果我们能每次把区间大小缩小到一半，就可以达成目标时间复杂度了。

既然要每次缩小一半，那肯定和区间中点有关嘛。我们不妨取某一个区间的中点，然后怎么办呢？

我们可以在另一个序列中查找这个中点的值所在的位置，这两个位置把两个区间分别分为“前段”和“后段”。如果“前段”中的数的个数大于 $k$，那么可以删除“后段”；如果“前段”中的数的个数不足 $k$，那么可以删除前段并把 $k$ 减掉前段中数的个数。如果我们每次都选较长的区间，那么这两个区间的长度的最大值在两次查找后一定会折半，结合二分查找，总复杂度 $T(n)=T(\frac{n}{2})+O(\log n)$。要粗略地解这个递推式，假设 $n=2^t$，那么 $T(n)=1+2+\cdots +t=O(t^2)$，于是复杂度是 $O(\log n\log n)$，还没有达到要求。

怎么办呢？瓶颈当然是二分，于是我们不能用二分。

每次取两个序列的中点 $a_i$ 和 $b_j$，不妨设 $a_i\le b_j$。如果 $i+j\le k$，那么第 $k$ 大一定不在 $a$ 的后半；否则第 $k$ 大一定不会在 $b$ 的前半，并且 $k$ 要减去 $b$ 前半的长度。每一次至少有一个区间长度减半，经过两次长度的最大值必定减半，$T(n)=T(\frac{n}{2})+O(1),\ T(n)=O(\log n)$，满足要求。

Ants

据说这是一道网络流？

当然也可以用分治配合计算几何技巧（极角排序）解决。

这里就不多说了（因为我不会计算几何(bushi）。

平面最近点对

这道题在进阶指南题目总结里有很好的总结，这里略。