NOI 二轮复习 I：深入分析问题

本文是 NOI 二轮复习的第一篇，总结了一些分析问题的基本套路。

问题的转化

常见的情况是：原问题不好处理，我们将其转化为其它形式的问题。

操作转化

将操作用形象的方式描述出来。

[ARC110E] Shorten ABC

Portal.

如何用一种方便的方式刻画操作？考虑将 $a,b,c$ 对应成 $1,2,3$，发现操作相当于用 $x\oplus y$ 替换 $x,y$。

那么直接倒序 DP，转移的时候注意转移最小的前缀就可以了，因为这样的方案是转移其它前缀的超集，注意如果初始时不能启动那么答案是 $1$。代码。

实例

我们看一些例子，来说明如何用“套路”去解决问题。

计数 1

计数题组 1。

[AGC046D] Secret Passage

Portal.

看上去很容易算重，但是一次删两个，发现只需要考虑一个后缀，加入 $j$ 个 $0$，$k$ 个 $1$ 能得到的字符串个数，本身就不会算重。直接转移，$1$ 后面放 $0$，$0$ 后面放 $1$ 即可。

然后计算合法的方式也是容易的，直接转移：

• 自己干掉自己，放在序列开头；
• 开头两个删掉一个，将另一个保留；
• 从已知中拿出一个来保留序列开头。

代码。

[AGC008F] Black Radius

Portal.

看上去怎么都得数重？排除掉全黑的情况，钦定我们在状态相同的时候，只数那个 $d$ 最小的。不难发现，这时对应的染色点是唯一的。

也即是说，设 $f(u,d)$ 代表 $u$ 的大小为 $d$ 的邻域，那么 $f(u,d)$ 被计入答案，当且仅当不存在与 $u$ 相邻的点 $v$ 使得 $f(u,d)=f(v,d-1)$。要不出现这种情况，应该满足以 $u$ 为根的次小深度子树深度 $\ge d-1$。

由于有的点不可以取到，因此相当于它存在一个最小合法 $d$，满足存在 $d_0$ 使得 $S(v,d_0)=S(u,d)$。也就是说，$d$ 的下限为所有含有 $1$ 的子树的深度的最小值。代码。

数据结构

数据结构题。

[P9152] 待黑白分明

Portal.

在集合中两个相邻的城市 $i,j$（假定 $i<j$）应该满足 $\min\{a_i,a_j\}>\max_{k=i+1}^{j-1}a_k$。

式子中后面这个东西抽搐的样子不难想到将其扔到大根笛卡尔树上。

考虑 $i,j$ 在树上的位置，它们一定存在祖先关系，否则它们的 LCA 就把限制干烂了。如果说 $j$ 是 $i$ 的祖先，那么 $i$ 应该在 $j$ 左儿子的右儿子链上，否则这条链上的点会把限制干烂。当然这里钦定了 $i<j$，否则在右儿子的左儿子链上也是可以的。

考虑到 $S$ 的选取条件是按照高度排序，这里钦定从大到小排序，相邻的节点必然满足 $a$ 是 $b$ 的祖先，且 $b$ 在 $a$ 的左儿子的右儿子链或者右儿子的左儿子链上。

如何处理单次询问？考虑树形 DP，令 $f_x$ 代表以 $x$ 开头的合法子集数量，$g_{x,0/1}$ 代表 $x$ 左儿子链/右儿子链的 $f$ 值的和，直接计算 $f_x=g_{x,0}+g_{x,1}+1,g_{x,0}=g_{ls_x,0}+f_x$ 即可，初始时只给在询问区间内的 $f$ 初始化，然后树形 DP 一次即可。

扫描线维护值域维，从大到小依次加入新的数并重新计算 $f$ 的值，然后较大数不会影响小数的答案，因此直接树状数组上查询即可。

若数据随机，那么每个数在笛卡尔树上的期望深度是 $O(\log n)$ 的，因此直接暴力维护就是对的。

使用树上随机撒点分块，预处理出每个关键点 $+1$ 后对每个点 $f/g_0/g_1$ 对于每个点 $f$ 造成的影响并统计影响的树上前缀和，然后每次修改先暴力改到关键点，这一部分是 $O(\sqrt{n})$ 的，然后跳 $O(\sqrt{n})$ 次，打一个标记，并同时统计 $f$ 的前缀和。查询的时候枚举所有关键点，将所有 $f$ 加起来即可。

时间复杂度 $O(n\sqrt{n}+q\sqrt{n})$，空间复杂度 $O(n\sqrt{n})$ 。逐块处理可以做到 $O(n)$ 的空间，这是最常规的思路。

也有其它做法，这里写一种。

首先我们要求出序列中每个值的左边和右边分别第一个大于它的值 $l_i,r_i$。

按照高度的值域进行分块。提前预处理出从某个点出发，到达和当前点同块的所有方案数 $sum_i$，以及某个点到达它左边和右边两个方向第一个和当前值不属于一个值域块的方案数 $suml_i ,sumr_i$，以及它们所对应的位置 $lid_i,rid_i$。可以 $O(n)$ 完成。

修改时将预处理好的值扔到下一个块里，更新 $g_i$ 代表第 $i$ 个值域块所影响的值域前缀（$1\sim R_i$）的答案。其只会跳最多不超过两倍块数次。同时可以处理出比 $i$ 小的值跳到 $i$ 的方案数 $f_i$。

每次查询，因为小的值每加入，所以直接从小到大加上区间包含的所有整块的方案 $g_{id}$。然后就是唯一的那个散块，直接暴力 DP 即可，时间复杂度 $O((n+q)\sqrt{n})$，空间复杂度 $O(n)$。代码。

综合应用

挑战自我吧！

[NOI2023] 桂花树

Portal.

首先考虑 $m=1$，发现答案是 $2n-1$。

对于 $m=2$，如果 $k=0$，那么发现就是再乘上 $2n+1$，根据此容易推测出 $k=0$ 的规律。

考虑 $k>0$ 有什么用，样例解释给了我们答案，可以直接分裂出一个空白节点，然后再填上一个节点。

由于 $k$ 很小，对需要填写的空白节点状压，直接转移即可。代码。