梅花侍从

idea, solution, std, data from GeZhiyuan

直接做肯定不好做，我们考虑分析一下结构。对于划分出来的两组，我们观测其在 $x$ 中的相对位置关系，分别用 X 和 O 表示两组内元素的位置，发现有意义的只有 XXOOOX 和 XXXOOO 两种。其他的可以进行如下替换：

XXOXOO -> XXXOOO
XXOOXO -> XXOOOX
XOXXOO -> XXOXOO -> XXXOOO
XOXOXO -> XXOOXO -> XXOOOX
XOXOOX -> XXOOOX
XOOXXO -> OXOXXO => XOXOOX -> XXOOOX
XOOXOX -> XOOXXO -> OXOXXO => XOXOOX -> XXOOOX
XOOOXX -> OXOOXX => XOXXOO -> XXOXOO -> XXXOOO

如上的每一次转变都显然严格不劣，至此我们分析出了所有可能的位置关系，实际上也正对应这前两组小样例的情况。由于可行的两种相对位置较为特殊，于是直接区间 dp 即可，记录 $f_{l, r}$ 表示 $x_l , x_{l+1}, \dots, x_r$ 划分的答案。复杂度 $O(n^3)$。

方片骑士

idea, solution, std, data from GeZhiyuan

小插曲

本题为我在验 Problem - 2006E - Codeforces 时看错题得到的产物，并在当时进行了查重，但由于跨度的时间过长，没想到在最近的一场 CF Div.2 中出现了此题的弱化版 Problem - 2031E - Codeforces。但是好在那题的做法虽然是正解的一部分，但也只能多通过 Sub2 获得 $15$ 分，并且作为萌萌的第二题本来也是希望能给大家送足够的分。但作为出题人的查重失误还是在此处给被影响到的所有人深深致歉。

算法 I

不难看出最终的树每个结点实际上都对应了原树的一个连通块。因此我们先假设定好根，然后进行如下动态规划：

• $f_u$ 表示 $u$ 这棵子树，以 $u$ 为根的树至少需要多大的满二叉树收缩得到，同样的大小为 $s$ 则记录 $\log_{2}{(s+1)}$ 的值。

直接合并即可，有：

• 如果 $u$ 只有一个儿子 $v$，则 $f_u = f_v + 1$。
• 否则令 $u$ 的儿子集合为 $S$，$f_u = \lceil \log_2 (\sum_{v \in S} 2^{f_v}) \rceil$

直接枚举根并进行动态规划，可以做到 $O(n^2)$，如果不拼链和菊花，预计得分 $30$。

算法 II

考虑进行换根，记录：

• $g_u$ 表示去除 $u$ 这棵子树，并以 $u$ 的父亲为根的树至少需要多大的满二叉树收缩得到，同样的大小为 $s$ 则记录 $\log_{2}{(s+1)}$ 的值。

考虑换根时动态维护 $\sum_{v \in S} 2^{f_v}$，相当于先将所有信息加入进去，然后每次查询如果删除一个的贡献是什么。

直接暴力找前驱后继可以做到 $O(n \sqrt n)$，预计得分 $50$ 至 $75$；也可以用线段树维护，复杂度 $O(n \log n)$，预计得分 $75$ 至 $100$。

也可以先将所有信息加入，然后记录二进制下的最高位，次高位，次次高位的位置，通过一系列分类讨论可以做到 $O(n)$。

算法 III

算法 II 实际上非常愚蠢，因为可以观察到，本题不需要询问每个根的答案，只需要知道所有根的最小值。

因此考虑换根时递归到 $u$ 时，对于所有 $u$ 的儿子 $v$，只有 $f_v$ 最大的才可能成为更优的根，其他的无需递归，因此这样暴力做就是 $O(n)$ 的，常数优秀的同时非常好写，预计得分 $100$。

算法 $\pi$

这题好像处理的方法非常多，欢迎大家在下方讨论。

可能有一些极快或者我没有料到的 $O(n \sqrt n)$ 也通过了此题。（真实性存疑）

还有高手

正如 小插曲中 所说，本题为我在验 Problem - 2006E - Codeforces 时看错题得到的产物。与那题相同，本题也可以支持像那题一样每次添加一个叶子并进行询问！但由于过于毒瘤还是选择了当下的版本。 你可以试试能解决 $n \leq 2 \times 10^5$ 并动态增加叶子的版本吗？

以下是来源于 huahua 的做法：

我们先把询问离线，把最终树的结构拿到，然后对树进行树剖，进行 ddp。

考虑 ddp 需要什么，我们对于每个结点 $u$，先对其所有轻儿子建立一棵线段树，维护轻儿子的 $\sum 2^{f_v}$ 在二进制下的值。

然后我们再考虑加入重儿子，对于没有轻儿子的显然好处理，否则假设重儿子的 dp 值为 $x$，而 $\sum 2^{f_v}$ 的最高位为 $a$，次高位为 $b$。

对于不存在 $b$ 的情况：

• 如果 $x > a$ 则 $f_u = x+1$。
• 否则如果 $x \leq a$ 则 $f_u = a+1$。

对于 $b = a - 1$ 的情况，我们令 $c$ 为最小的满足 $\sum 2^{f_v}$ 在二进制下第 $[c, a]$ 都为 $1$ 的非负整数：

• 如果 $c$ 不是最低位：
  • 如果 $x > a$ 则 $f_u = x+1$。
  • 如果 $c \leq x \leq a$ 则 $f_u = a+2$。
  • 如果 $x < c$ 则 $f_u = a + 1$。
• 如果 $c$ 是最低位：
  • 如果 $x > a$ 则 $f_u = x+1$。
  • 如果 $c < x \leq a$ 则 $f_u = a+2$。
  • 如果 $x \leq c$ 则 $f_u = a+1$。

对于 $b < a-1$ 的情况：

• 如果 $x > a$ 则 $f_u = x+1$。
• 如果 $x = a$ 则 $f_u = a+2$。
• 如果 $x < a$ 则 $f_u = a+1$。

不难发现在所有情况下，$f_u$ 始终是一个关于 $x$ 的至多三段的分段函数，始终为最后一段为 $x$ 上系数为 $1$ 的一次函数，且除最后一段外为常函数。

然后我们再次观察这个转移的特点，我们尝试观察对于一段重链，令链首为 $t$，而我们在链末传入的 $x$ 和最终 $f_t$ 是什么关系呢？实际上仍然是满足如上条件的至多三段分段函数！

于是我们就解决了非换根的问题，对于每条重链我们也建立一棵线段树去维护函数的复合，总复 $O(n \log^2 n)$。利用全局平衡二叉树的技巧可以做到 $O(n \log n)$。

对于换根的问题实际上是简单的，这种 ddp 本身也支持换根，且不难发现在加入叶子的过程中，最优的根只有两种可能，不动或者沿着原根到新加入的叶子的路径移动 $1$ 步。至此我们在 $O(n \log n)$ 或 $O(n \log^2 n)$ 内解决了该问题。

红桃王后

idea, solution, std, data from xianhz

子任务 I

我会暴力枚举/分类讨论！

直接枚举每轮是哪些人获胜，或者直接把 $n\leq 3$ 的情况画出来逐一判断，这些都是可行的。

总之只要是正确的做法大概都能通过这档部分分。

子任务 II

我会观察性质！

考虑建图 $G$， 对于所有关系 $u$ 战胜 $v$ 连一条有向边 $u\to v$。

注意到对于一个合法的图，必要条件有：

• 是个 DAG。（若 $u$ 战胜 $v$ 则 $u$ 的排名会严格比 $v$ 高）
• 有恰好一个点没有入边只有出边。（即第一名是全胜的）
  • 实际上易发现有 $i$ 条入边的有恰好 $\binom ni$个人。
• 第一名直接或间接战胜了所有人，其中 $u$ 直接或间接战胜 $v$ 可以理解为图中存在一条从 $u$ 到 $v$ 的路径。

所以对于每一轮的败者，在他们在败者组中决出的第一名（设为 $A$ ）在原图中恰有一条入边，且一 个人在败者组当且仅当它在 $A$ 的可达集合中。

所以对于每一轮不再枚举哪些人获胜，而是只在恰有一条入边的点中枚举 $A$ 即可。复杂度 $O(n!2^n)$。

子任务 III

我会对暴力记忆化！

在刚才搜索的过程中加上记忆化，即维护 $f_S$ 表示如果集合 $S$ 内的人参加比赛是否存在合法方案。

这看上去作用有限，甚至是个负优化，但你如果把它加上就会发现自己莫名其妙通过了这个子任务。

你可能会质疑出题人的数据强度。（好吧可能确实需要质疑）但这个做法的复杂度其实是有保证的。

子任务 IV

我知道记忆化为什么是对的！

考虑再建反图 $G_r$，对于所有关系 $u$ 战胜 $v$ 连一条有向边 $v\to u$，由对称性它也满足我们之前推的所有性质。

考虑去分析状态数：注意到对于一个 $f_S=1$ 的 $S$，它一定由 $S$ 中的第一名在 $G$ 中的可达集合 与 $S$ 中的最后一名在 $G_r$ 中的可达集合 的交生成。

说人话一点就是：如果你知道了 $S$ 中的第一名和最后一名你就可以唯一确定 $S$ 了，所以合法的 $S$ 的数量是不超过 $O(2^{2n})$ 的，这也是对刚才记忆化的复杂度的证明。

所以你去拿 $dp_{i,j}$ 表示：由 $i$ 和 $j$ 生成的 $S$ 在 $G$ 中的导出子图是否合法。

让我们再分析一下状态数。

最坏情况是：第 $i$ 个人直接或间接战胜了所有 $i\subset j$ 的 $j$，直接或间接输给了所有 $j\subset i$ 的 $j$。（这里将 $i$ 视作的集合就是 0-index 时 $i$ 在二进制下的表出）

这时我们会搜索到一个元素当且仅当 $f_S=1$。而合法的 $S$ 能由一对 $i\subset j$ 的 $(i,j)$ 生成，而对于一对 $(i,j)$ 的转移复杂度应该是 $O(2^{|j\setminus i|}n^2)$

通过组合意义可证明复杂度是 $O(4^nn^2)$，这也给出了该题计数版本的一个多项式级别做法。

当然如果你对于子任务 3 的记忆化直接使用 xor hashing 存储状态，应该也可以通过该子任务，但代价呢？（upd：好吧因为是 IOI 赛制所以没法有什么代价）

子任务 V

我会猜结论！ 虽然上面的做法看上去很妙，但只用上述性质的话恐怕没法优化复杂度了。$3^n$ 级别的状态数让我们不得不借助题目本身的性质来优化 dp。

注意到若 $(i,j)$ 能被合法划分成 $(i,k_1),(l_1,j)$ 和 $(i,k_2),(l_2,j)$，则 $dp_{i,k_1}=dp_{l_1,j}=1$ 时必有 $dp_{i,k_2}=dp_{l_2,j}=1$，此时有 $dp_{i,j}=1$（这里合法划分的意思是两个集合间的边是一组完美匹配）

证明是容易的：考虑两个划分分别是 $A\oplus B,C\oplus D$ 和 $A\oplus C,B\oplus D$。

由更低阶的结论我们有 $f_A=f_B=f_C=f_D=1$，然后交换一下划分的顺序即可。

所以结论就是：我们只要能找到一组 $(i,k),(l,j)$ 使得这个划分在当前层没有矛盾，就可以往下递归，因为 $(i,k)$ 和 $(l,j)$ 一定都有合法解。

感性来说，就是我们不停划分会让每个子问题内部的限制更宽松，并且不会让一个之前原本可以使用的匹配变得不合法。（或者说就是无后效性）

所以我们直接枚举第 $2^{n-1}+1$ 名，去看它的可达集合和这个集合的补集之间的边是否是一组完美匹配即可判断。

复杂度 $F(n)=2^nn^2+2F(n-1)=O(2^nn^3)$。

子任务 VI

我会用位运算并行求可达集合与判断完美匹配！

考虑求可达集合无非是在一个有向图中，按一个边的顺序遍历，对于一条边 $(i,j)$，令 vis[j]|=vis[i]。

那么如果我们要求 个点的可达集合，就可以用位运算加速这个过程：对于第 $i$ 个点 $p_i$，初始令 $vis_{p_i}=2^i$，然后执行上述算法。

对于判断完美匹配方法也是类似的：对于一条边 $(i,j)$，令 d[i]+=vis[j]&~vis[i]， d[j]+=vis[j]&~vis[i]，最后判断是否所有 $d$ 都是 $1$ 。 由于我们只在乎 $d$ 是 $0$，$1$ ，还是 $\geq 2$ ，所以用两个值维护 $d_i$ 在第 $j$ 位是否 $\geq 1$ 和是否 $\geq 2$ 即可。

这样我们就将构造和计数复杂度分别优化成了 $O(2^nn^2)$ 和 $O(4^nn)$，足以通过本题。

黑桃国王

idea from wzc_IOI_czw, fast_photon, bunH2O; solution from zhoukangyang, Rainbow_sjy; std, data from LeafSeek, Melania

准备工作

• 如果一条有向边 $u\to v$ 不出现在任何一个回路中（两个端点处在不同的强连通分量），可以直接删去这条边。
• 如果一个结点 $u$ 不出现在任何一个回路中（处在单独一个结点的强连通分量并且没有自环），可以直接删去这个结点。

删去这些东西以后，从任何一个结点 $u$ 出发，无论前面怎么走后面一定能走回去。也就是说：对于回路的一个可空的前缀 $u_0\to u_1\to\cdots\to u_i(i\geq0)$，一定能找到一个非空的后续 $u_i\to u_{i+1}\to\cdots\to u_ℓ(ℓ\geq i+1)$，使得 $u_ℓ=u_0$。

最小无穷路径

定义 $s(u,i)$ 表示从 $u$ 开始游走 $i-1$ 步形成的字符串里面字典序最小的那个。

定义 $f(u,i)$ 表示 $s(u,i)$ 在 $s(1,i)\sim s(n,i)$ 里面去重之后的排名。

根据定义 $s(u,i)=a_u+\min\limits_{u\to v}s(v,i-1)$。

因此我们可以递推 $f(u,i)$ 等于二元组 $\left(a_u,\min\limits_{u\to v}f(v,i-1)\right)$ 在所有 $n$ 个（第 $i$ 步的）二元组里面去重之后的排名。

如果递推到了某个 $i$ 我们发现所有 $f(u,i)=f(u,i-1)$，那么 $f(u,+\infty)=\cdots=f(u,i+1)=f(u,i)=f(u,i-1)$。

注意到 $f(u,i)$ 不同的两个 $u$ 后面永远不会合并，而相同的两个 $u$ 后面有可能会分开。因此这个 $i\leq n$。

我们把 $s(u,+\infty)$ 称作 $u$ 的最小无穷路径。上面的算法可以在 $O(mn)$ 的时间内求出所有最小无穷路径。

性质 I

考虑刻画所有 $n$ 个最小无穷路径形成的结构。

假设最后有 $m$ 个不同的最小无穷路径（即 $f(1,+\infty)\sim f(n,+\infty)$ 的值域是 $1\sim m$）。

那么可以建出一个有 $m$ 个结点的根向环套树森林，每个结点上面写有一个字符，同时有唯一的一条出边指向另外一个结点。对于原图中的某个结点 $u$，森林中的结点 $f(u,+\infty)$ 的唯一出边指向的就是 $\min\limits_{u\to v}f(v,+\infty)$。

在这个根向环套树森林当中，（去重之后的）排名为 $i$ 的最小无穷路径等于从结点 $i$ 出发沿着出边一直游走形成的无穷字符串。

由于所有 $m$ 个无穷字符串是两两不同的，我们的根向环套树森林一定满足以下两个性质：

1. 每个环 $C$ 一定不存在非整串的非空周期。
2. 每个结点 $u$ 的所有入度 $v_i$，上面写有的字符一定两两不同。

算法 I

固定一个起点 $u$，考虑所有 $u_0=u_ℓ=u$ 的回路生成的无穷字符串构成的集合 $S_u$。

• 如果最小无穷路径是一个纯循环 $o$ 形（意味着 $f(u,+\infty)=C^\infty$），那么 $S_u$ 有一个 最小值 $C^\infty$​：

  1. 如果 $S_u$ 里面包含唯一一个元素，那么 $C^\infty$ 可以属于序列 $s_1\sim s_k$；

  2. 只要 $S_u$ 里面包含至少两个元素，那么 $C^\infty$ 可以属于序列 $s_1\sim s_k$，但是序列 $s_1\sim s_k$ 里面不能包含任何 $>C^\infty$ 的字符串 $X$。

     （这是因为对于任何一个字符串 $X>C^\infty$，一定存在一个 $Y\in S_u$ 满足 $X>Y>C^\infty$。）

• 如果最小无穷路径是一个混循环 $\rho$ 形（意味着 $f(u,+\infty)=A+C^\infty$），那么 $S_u$ 有一个 不在 $S_u$ 中的下确界 $A+C^\infty$：

  1. 此时 $S_u$ 里面包含至少两个元素，当然序列 $s_1\sim s_k$ 里面不能包含任何 $>A+C^\infty$ 的字符串 $X$。

     （这是因为对于任何一个字符串 $X>A+C^\infty$，一定存在一个 $Y\in S_u$ 满足 $X>Y>A+C^\infty$。）

对于上述三种情况，我们分别把 $u$ 称作一个第零类／第一类／第二类结点。

最后我们计算答案。我们依次枚举 $i\in\{1,2,\cdots,m\}$，考虑 $f(u,+\infty)=i$ 的所有结点 $u$：

• 只要其中存在第二类结点，那么确定答案 $=i-1$，跳出循环；
• 否则如果存在第一类结点，那么确定答案 $=i$，跳出循环；
• 否则如果全部都是第零类结点，那么继续循环。

这里有一个小问题：我们已知一个结点 $u$ 的最小无穷路径是一个纯循环 $o$ 形，怎么判断它是一个第零类结点还是一个第一类结点？

我们考虑 $u$ 所在的强连通分量。只要这个强连通分量内存在一个生成不同字符串的回路，那么所有 $o$ 形都是第一类结点。

对于每一个强连通分量，我们刻画这个条件：拿出这些结点对应的无穷字符串排名。如果它们形成单独一个环，并且整个强连通分量内的任何一个结点 $u$ 所有出边 $u\to v$ 满足 $f(v,+\infty)$ 全部相同，那么所有 $o$ 形都是第零类结点；否则所有 $o$ 形都是第一类结点。

算法 I 的时间复杂度为 $O(mn)$，可以获得至少 $39$ 分。

枚举每个强连通分量，在其中刻画这个条件：拿出这些结点对应的无穷字符串排名。如果它们形成单独一个环，并且整个强连通分量内的任何一个结点 $u$ 所有出边 $u\to v$ 满足 $f(v,+\infty)$ 全部相同，那么所有 $o$ 形都是第零类结点；否则所有 $o$ 形都是第一类结点。

算法 I 的时间复杂度为 $O(mn)$，可以获得 $39$ 分或者更多。

算法 II

直接把算法 I 中计算 $f(1,+\infty)\sim f(n,+\infty)$ 的过程换成启发式分裂即可。

我们讲的具体一点。固定一个时刻，考虑关于 $s(1,+\infty)\sim s(n,+\infty)$ 的大小顺序我们掌握的信息。

我们开一棵二叉树 $T$ 来记录所有的信息。以下我们说明这棵二叉树 $T$ 的具体结构：

• $T$ 中的每个结点代表 $G$ 中的一个结点集合。
• $T$ 中的每个结点代表的集合等于它的两个儿子的并集。特别的，根结点代表全集 $\{1,2,\cdots,n\}$。
• 对于两个 $G$ 中的结点 $u,v$，如果 $T$ 的 DFS 序中 $u$ 严格位于 $v$ 的左侧，那么说明 $s(u,+\infty) < s(v,+\infty)$。

在上述结构中，$T$ 的所有叶子结点代表的集合一定构成了 $\{1,2,\cdots,n\}$ 的一个划分。我们可以看到：只要两个 $G$ 中的结点 $u,v$ 处在不同的集合中，它们的大小顺序就是已知的。同一个集合内部的结点，它们的大小顺序在这个时刻是未知的。

对于一个 $G$ 中的结点 $u$，如果 $T$ 中的结点 $x$ 代表的集合包含了 $u$，我们就认为 $u$ 属于 $x$ 这个 等价类（这刻画了一个等价关系）。

每次进来一个新的信息，我们分裂 $T$ 的某个叶子结点 $x$ 产生左右两个子结点 $y,z$，表示我们已经知道 $y$ 等价类小于 $z$ 等价类。

最初的时候我们只根据 $a_u$ 建一个毛毛虫，每次把拥有最小字母的结点集合扔到左边，把剩下的结点集合扔到右边继续建毛毛虫。

我们希望持续使用 $T$ 作为证据更新自身，直到得到 $T$ 不能再更新的最终形态为止。

我们另开一棵二叉树 $T'$ 表示我们已经处理的结点。$T'$ 一直是 $T$ 包含根结点的一个连通块（最初 $T'$ 只包含根，最终 $T'=T$）。

考虑尽量简洁的储存 $T,T'$ 的形态。经过一番探索，我们发现维护以下三个数组是最好的办法：

• $f_u$ 表示结点 $u$ 所在的 $T$ 等价类编号；
• $g_u$ 表示结点 $u$ 的所有出度 $v$ 所在的 $T'$ 等价类当中（字典序）最小的等价类编号；
• $\text{cnt}_u$ 表示拥有这个最小值的出度 $v$ 一共有多少个。

对于一个静止的时刻（没有正在处理的结点），一定有 $f_u$ 等于二元组 $(a_u,g_u)$ 在所有 $n$ 个二元组中（去重之后的）的排名。

我们维护一个队列 $Q$。每次 $T$ 的某个叶子结点 $x$ 被分裂，我们立刻把它推入队列的队尾。

我们每次取出队头结点 $x$（现在 $\in T'$），假设它的两个儿子叫做 $y,z$（现在 $\not\in T'$）。

第一步是正确更新所有 $g_u,\text{cnt}_u$ 的值。对于每个 $g_u=x$，更新之后 $g_u=y/z$ 都有可能：

• 如果结点 $u$ 的 $\text{cnt}_u$ 个出度 $v$ 中存在一个属于 $y$ 等价类，那么更新 $g_u=y$；
• 如果结点 $u$ 的 $\text{cnt}_u$ 个出度 $v$ 全部都属于 $z$ 等价类，那么更新 $g_u=z$。

第二步是正确更新所有受影响的 $T$ 等价类。一个等价类内的所有结点都拥有相同的 $f_u$，本来拥有相同的 $g_u=x$，现在 $g_u=y/z$。

• 这个等价类内 $g_u$ 等于 $y$ 的，$f_u$ 新建一个白色结点作为 $f_u$ 的左儿子。
• 这个等价类内 $g_u$ 等于 $z$ 的，$f_u$ 新建一个白色结点作为 $f_u$ 的右儿子。

最后我们实现启发式分裂。启发式分裂的含义是把较小的集合分裂出去，留下较大的集合。每次在 $T$ 中划分一个叶子结点 $x\to y/z$ 的时候，我们让 $y,z$ 之一等于 $x$。然后我们对于 分裂出去的是左儿子 和 分裂出去的是右儿子 两种情况，分别采用不同的实现方法。实现的时候，对于 $x\to y/z$，我们枚举那个被分裂出的集合的每个结点，再枚举它们的所有入度，即可更新到所有需要更新的等价类。

算法 II 的时间复杂度为 $O(m\log n)$，可以获得 $100$ 分。

珍珠守卫

idea, solution, std, data from LeafSeek, Melania

算法 :)

写一些似是而非的区间 DP。对于 sub 1~4，我已经拿了许多选手赛时提交的代码与搜索对拍，很容易拍出 hack 数据。

时间复杂度 $O(n^3 \text{poly}(m,k))$，赛时数据可以获得 $1 \sim 40$ 分。

算法 I

操作模型 I

我们假设存在一个最优操作方案同时符合以下两个描述：

1. 如果两颗相邻珠子颜色相同，我们一定不会把它们分隔开。
2. 我们只会进行一种加长操作。加长操作首先选定一颗珠子 $(a_i, c_i)$，然后不断插入一颗质量为 $1$ 的同色珠子，目的是以它为中心开启一个消除过程。我们不断地对剩余序列进行这种加长操作直到删空序列。

我们首先刻画所有符合操作模型 I 的方案统一具有的结构，然后针对这种结构设计一个区间 DP 计算出最小的操作次数 $q$。

结构模型 I

根据假设 1，对于所有极长同色区间 $[l, r]$，我们可以把 $(a_l, c_l) \sim (a_r, c_r)$ 这些珠子合并成一颗珠子 $\Big( a_l, \min \Big( \displaystyle\sum_{i=l}^r c_i, k-1 \Big) \Big)$。

合并同色区间简化了我们的问题，现在我们在所有 $a_i \neq a_{i+1}$ 的新序列上刻画结构。

考虑一个消除步骤同时消除掉的珠子。排除掉最后插入的几颗质量为 $1$ 的珠子，剩下的一定是初始序列的一个子序列，我们用一个集合 $S$ 表示它包含了原序列中的哪些位置。对于一个方案，我们用一个集合族 $\boldsymbol{\Omega}$ 表示所有消除步骤对应的 $S$ 构成的集合。

以下我们列出了 $\boldsymbol{\Omega}$ 一定满足的五个性质（必要条件）。事实上，只要一个集合族 $\boldsymbol{\Omega}$ 同时满足所有五个性质，那么它一定能够还原一个符合操作模型 I 的方案（充分条件）。具体怎么还原方案读者可以自己思考。

1. $\boldsymbol{\Omega}$ 一定形成了 $\{ 1, 2, \cdots, n \}$ 的一个划分，每个位置恰好属于 $\boldsymbol{\Omega}$ 中的一个集合 $S$。
2. 对于两个不同集合 $S, T \in \boldsymbol{\Omega}$，一定不会存在四个位置 $a < b < c < d$ 使得 $a, c \in S$，$b, d \in T$。
3. 对于一个集合 $S \in \boldsymbol{\Omega}$，假设 $S = \{ p_1, p_2, \cdots, p_t \}$（$p_1 < p_2 < \cdots < p_t$），那么 $a_{p_1} = a_{p_2} = \cdots = a_{p_t}$。
4. 对于一个集合 $S \in \boldsymbol{\Omega}$，假设 $S = \{ p_1, p_2, \cdots, p_t \}$（$p_1 < p_2 < \cdots < p_t$），那么以下两个一定成立一个：
   • $ \displaystyle\sum_{i=1}^t c_{p_t} \leq k-1$。
   • $ \displaystyle\sum_{i=1}^t c_{p_t} \geq k$。但是存在一个整数 $t' \in [1, t-1]$ 使得 $ \displaystyle\sum_{i=1}^{t'} c_{p_t} \leq k-1$，$ \displaystyle\sum_{i=t'+1}^t c_{p_t} \leq k-1$。
5. 对于两个不同集合 $S, T \in \boldsymbol{\Omega}$，如果 $ \min(T) - \max(S) = 1$，我们连一条有向边 $S \to T$。那么 $\boldsymbol{\Omega}$ 中的所有集合被串成若干有向链。对于每一条有向链，以下两个一定成立一个：
   • 有向链的长度 $= 1$。
   • 有向链的长度 $\geq 2$，并且至少包含两种除了 $a_{l-1} = a_{r+1}$ 以外的颜色。

根据性质 4，我们又注意到一个操作方案的代价只跟 $\boldsymbol{\Omega}$ 有关，因此通过描述所有的 $\boldsymbol{\Omega}$，我们的区间 DP 当然就能计算出最小操作次数 $q$。

区间 DP 实现 I

我们可以使用以下几个 DP 数组进行区间 DP，具体转移留给读者自行思考。

• 开一个 DP 数组 $C(l, r)$ 表示 $(a_l, c_l)(a_r, c_r)$ 形成一个集合 $S$ 的两端，区间 $[l, r]$ 内部的最小代价。
• 开一个 DP 数组 $D(l, r)$ 表示 $(a_l, c_l)(a_r, c_r)$ 形成一个合法有向链的两端，区间 $[l, r]$ 内部的最小代价。
• 开一个 DP 数组 $F(l, r, x, 0/1)$ 辅助 $C$ 的转移。其中 $x$ 表示当前 $c_{p_i}$ 的和，$0/1$ 表示最后一步吃掉的是一个区间还是一个同色 $a_{p_i}$。
• 开一个 DP 数组 $G(l, r, x, 0/1)$ 辅助 $C$ 的转移。其中 $x$ 表示当前 $c_{p_i}$ 的和，$0/1$ 表示最后一步吃掉的是一个区间还是一个同色 $a_{p_i}$。
• 开一个 DP 数组 $P(l, r)$ 辅助 $D$ 的转移。表示当前有向链还没有出现除了 $a_{l-1}, a_l$ 以外的颜色。
• 开一个 DP 数组 $Q(l, r)$ 辅助 $D$ 的转移。表示当前有向链已经出现了除了 $a_{l-1}, a_l$ 以外的颜色。

时间复杂度 $O(n^3k)$，可以获得 $7$ 分。

第一类反例

1 1 2 1 1 3 4 1 1 1

1 1 2 1 1 3 4 1 [2] 1 1
1 1 2 1 1 3 4 1 2 1 1

1 1 2 1 1 3 [3] 4 1 2 1 1
1 1 2 1 1 3 3 4 1 2 1 1

1 1 2 1 1 3 3 [3] 4 1 2 1 1
1 1 2 1 1 >!< 4 1 2 1 1
1 1 2 1 1 4 1 2 1 1

1 1 2 1 1 4 [4] 1 2 1 1
1 1 2 1 1 4 4 1 2 1 1

1 1 2 1 1 4 4 [4] 1 2 1 1
1 1 2 1 1 >!< 1 2 1 1
1 1 2 >!< 2 1 1
1 1 2 2 1 1

1 1 2 2 [2] 1 1
1 1 >!< 1 1
>!<
win

第二类反例

11 222 3 4444 3333 22 1111 22 3333 4444 3 222 11

11 222 3 4444 3333 22 1111 [1] 22 3333 4444 3 222 11
11 222 3 4444 3333 22 >!< 22 3333 4444 3 222 11
11 222 3 4444 3333 22 22 3333 4444 3 222 11

11 222 3 4444 3333 22 [1] 22 3333 4444 3 222 11
11 222 3 4444 3333 22 1 22 3333 4444 3 222 11

11 222 3 4444 [4] 3333 22 1 22 3333 4444 3 222 11
11 222 3 >!< 3333 22 1 22 3333 4444 3 222 11
11 222 >!< 22 1 22 3333 4444 3 222 11
11 >!< 1 22 3333 4444 3 222 11
11 1 22 3333 4444 3 222 11

11 1 22 3333 4444 [4] 3 222 11
11 1 22 3333 >!< 3 222 11
11 1 22 >!< 222 11
11 1 >!< 11
>!<
win

算法 II

时间复杂度 $O\big(n^3\max(m,k)^3k^4\big)$，可以获得 $88$ 分。

算法 III

可以优化矩阵乘法。时间复杂度 $O\big(n^3\max(m,k)^2k^3\big)$，可以获得 $100$ 分。