首先作为管理员向大家谢罪，由于我们的准备失误（主要是我的锅），导致 Day2 的比赛准备出现了很大问题，D2T1 的数据甚至在比赛结束前也没有完全准备好，导致延误了评测时间，在此为造成大家不便表示歉意

提问系统

from Itst，数据，标程，题解 by Itst

超级良心的签到题！

算法一

我会暴力！枚举每次 push 的情况，复杂度 $O(2^{k}k)$，可以通过子任务一获得 $20$ 分。

算法二

$c_r=c_b=k$ 没有任何限制。直接枚举红颜色的元素个数，答案为 $\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})i(k-i{)}^2$，直接计算即可。可以通过子任务六，结合算法一获得 $25$ 分。

算法三

对于栈操作序列，我们可以构造一个树结构：初始只有一个节点，且有一个指针指在该节点。遍历每个操作，遍历到 push 操作时在当前指针处新加入一个儿子，并将指针指在该新加入节点处；遍历到 pop 操作时将指针移到当前指的节点的父亲处。可以发现这棵树很好地描述了栈的状态：每个时刻栈里面的元素对应树上从根到某个节点的一条链。那么限制就是每条链上 R 和 B 节点的数量不能超过 $c_r$ 和 $c_b$。注意根节点不需要选择 R 或者 B。

那么显然有暴力 DP：$f_{i,sr,sb,lr,lb}$ 表示处理了点 $i$ 的子树，子树内有 $sr$ 个 R 节点、$sb$ 个 B 节点、向下的链中 R 个数最大是 $lr$、向下的链中 B 个数最大是 $lb$ 的情况下的方案数。

当然直接暴力记录状态和合并是比较难通过的。有一些显然的优化：$lr$ 与 $lb$ 维度可以前缀和优化；最后 $sr+sb=k$ 所以可以省去一个。这样优化以后容易做到 $O(k^5)$ 或 $O(k^4)$，可以通过子任务二或三，结合算法二分别获得 $40$ 和 $55$ 分。

算法四

对于上述暴力 DP 有两个优化方向。同时使用两个优化方向则容易做到 $O(k^2)$，而仅使用一个则只能做到 $O(k^3)$。因此题解中不特别标注 $O(k^3)$ 做法。

首先考虑处理每个方案的贡献。设 $\mathrm{col}(i)$ 表示节点 $i$ 的颜色。注意到 $p_r{p}_b^2=\sum _{\mathrm{col}(i)=R}1\sum _{\mathrm{col}(i)=B}1\sum _{\mathrm{col}(i)=B}1$，也就是有序的选出 $1$ 个 R 点和 $2$ 个 B 点的方案数。

因此可以把对应 $sr$ 和 $sb$ 的状态删去，改为 $f_{i,lr,lb,0/1,0/1,0/1}$，其中 $lr$ 与 $lb$ 意义不变，三个 $01$ 分别表示一次选 R 和两次选 B 分别是否选中元素，使用背包合并这些维度，并且在每个节点确定颜色的时候确定对应位置的选择是否选它。

第二个优化方向是状态记录维度的翻转。更改 $lr$ 与 $lb$ 的意义为祖先中 R 和 B 节点的数量，合并和单点状态选择的转移都是比较简单的。值得注意的是状态翻转过后，对于 $f_x$ 总有 $lr+lb=de{p}_x$，因此其中一维可以直接省去，得到一个 $O(k^2)$ 的算法。

最后注意根节点不需要选择 RB 即可。可以通过所有子任务获得 $100$ 分。

答案查重

from jiqimao & mayaohua，数据，标程，题解 by mayaohua

算法一

对于 $n\le 7$ 的数据，我们可以暴力枚举染色方案，然后树哈希验证是否与之前枚举的方案均不同构（本质不同），树哈希的时候需要把颜色也加进去。

时间复杂度取决于你的树哈希算法，在 $O(n!\cdot n)$ 到 $O(n!\cdot n^3)$ 之间，期望得分 $10$ 分。

算法二

对于一条链的数据，容易发现自同构只有翻转一种，因此用 burnside 引理很容易得到答案就是 $\frac{(\genfrac{}{}{0ex}{}{n}{k})+[k=1\mathbb{and}2\nmid n]}{2}$。

时间复杂度 $O(n)$，期望得分 $5$ 分。

算法三

考虑比较靠谱的做法，注意到两棵带颜色的子树同构，那么它们忽略颜色后也必定同构，这提示我们考虑对子树 DP。

注意到颜色 $1$ 的位置令树变为有根树，那么我们不妨枚举所有作为根树不同构的节点，钦定它们染颜色 $1$ ，以它们为根分别 DP 计算答案。为了方便，我们采用 EGF 描述这个 DP，令 $f_i(x)$ 表示以 $i$ 为根子树关于染颜色点个数的 EGF，那么如果 $i$ 的所有儿子为根子树互不同构，显然有 $f_i(x)=(1+x)\prod _{u\in so{n}_i}{f}_u(x)$，而对于同构的子树，不妨设单一棵的 EGF 是 $g(x)$，总共有 $k$ 棵，那么我们可以得到总的 EGF 是 $\sum _{i=0}^k\frac{(g(x)-1{)}^i}{i!}$，对这个式子的理解是我们枚举非空的子树个数 $i$ 并填进去，然后当然要除去同构子树带来的影响 $i!$（你也可以考虑子树个数无穷多的情况帮助理解，这时候是 $e^{g(x)-1}$）。

那么我们直接暴力计算上面的 DP，用平方的暴力多项式乘法，用树上合并背包的套路可以分析出单次 DP 是 $O(n^2)$ 的，由于要枚举根总复杂度是 $O(n^3)$，结合算法二期望得分 $35$ 分。

算法四

算法三的一个复杂度瓶颈是我们枚举了所有的根，这是因为原来的树是无根树。考虑无根树同构的套路，我们尝试枚举重心来优化。

若树有唯一重心，那么可以直接以 $rt$ 定为根，对有根树进行计算，这样两个同构的方案此时作为有根树仍然是同构的。于是我们可以转成有根树，跑一次算法三的 DP，注意此时我们不假设根染颜色 $1$。

若树有两个重心，一定是一条边的两端，且两边子树大小相等。那么我们可以删去这条边，分别以两个重心为根做一次上面的算法，若两边子树不同构，显然可以直接乘起来，否则令一侧的 EGF 是 $g(x)$，总共就是 $g(x)+\frac{(g(x)-1{)}^2}{2}$，你也可以理解成是在边中间加了一个虚点，并以虚点作为唯一重心计算。

同样使用暴力多项式乘法，时间复杂度是 $O(n^2)$，结合算法二期望得分 $45$ 分。

算法五

考虑对算法四进行优化。注意到算法三时提到的一个重要性质，若对某个点 $i$ 的儿子 $u$ ，不存在另一个 $i$ 的儿子 $v$ 使得它们的子树同构，那么 DP 转移时我们在 $f_i(x)$ 会直接乘上 $f_u(x)$。

那么我们若对有根树做一个特殊的轻重链剖分——只保留严格重儿子，由于每个严格重儿子都不会有另一个儿子子树与它同构，那么转移是直接乘上去的。再考虑优化多棵同构子树的合并，这要求我们对一个 $g(x)$ 和一个 $k$ 快速求出 $\sum _{i=0}^k\frac{(g(x)-1{)}^i}{i!}$，容易发现这个式子可以对指数 $i$ 分治 FFT，令 $deg(g(x))=m$，则单次计算的复杂度为 $O(mk\log (mk)\log k)$。那么我们递归计算，只在链顶处保留真实的 $f_i(x)$，并对链上每个节点，若它有出现次数 $>1$ 的子树，用上面的方法计算出合并后的 EGF，这样只需要把所有跟这条链相关的 EGF 全部乘起来（链上每个点的 $1+x$ 也要计入）就能得到链顶的 EGF 了，乘起来的时候同样分治 FFT，但这里更优秀的做法是用哈夫曼树计算一个最优合并顺序并乘起来。

考虑这样做的时间复杂度，不难发现这个做法实际上是一个全局平衡二叉树上的分治 FFT（合并多个同构子树时的 $\log k$ 可以理解成子树大小每次加倍），因此总时间复杂度是 $O(n{\log }^{2}n)$，期望得分 $100$ 分，可以通过。理论上在链上把 EGF 乘起来的时候如果直接对下标分治 FFT，最坏时间复杂度是 $O(n{\log }^{3}n)$，但常数非常小，同样可以通过。如果你某一步写挂了或处理错了，可能只能得到 $65\sim 85$ 分。

排名预测

from p_b_p_b，数据，标程，题解 by p_b_p_b

在 UOJ 上出的第一道题！

题面和样例都出了点小锅，不过应该没造成太大影响吧。

算法零

哎嘿，出题人没在样例里放无解的情况，暗示一定有解？

直接输出初始树的 dfs 序。

期望得分：$0$。

算法一

我会爆搜！

从给出的 $a$ 倒着搜索，复杂度 $O(n!\text{ poly}(n))$。第一个包只有 $n\le 8$，所以应该可以轻松通过。

期望得分：$10$。

算法二

考虑倒 Y 的情况，此时 ddm 序只有两种，我们分别判断。

设 $p$ 有两个儿子，分别引出链 $L_1$ 和 $L_2$，且 $L_1$ 的 ddm 序先于 $L_2$。设 $1\sim p$ 的链为 $L$。

因为只能把父亲较小的 $b$ 往下换，所以容易发现 $L_2$ 的 $b$ 一定无法进入 $L_1$ ，最优策略一定是先在 $L\cup L_1$ 上操作，把 $L_1$ 调整为 $a$，然后再操作 $L_2$。

所以一个 ddm 序合法当且仅当 $L_1$ 的 $a$ 全部在 $L\cup L_1$ 的 ddm 序中出现过。

期望得分：$30$。结合算法一期望得分 $40$。

算法三

考虑保证合法解是给定 ddm 序的情况。（我只说了合法当且仅当给定 ddm 序合法，没要求 std 也输出给定 ddm 序啊！）

这提示我们必须找到判断一个 ddm 序是否合法的方法。

通过打表手玩找规律 and/or 严谨证明，可以发现：对于每一个 $i$ ，把 $\ge i$ 的数替换为 $1$， $<i$ 的数替换为 $0$，那么一个 ddm 序合法当且仅当在每个 $i$ 的 $01$ 情况中合法。

如何判断 01 情况是否合法呢？从 $a$ 倒着推，贪心地往下塞就好了。写的好看一点就是合法当且仅当对于每个 $x$， $x$ 子树在 $a$ 中的 $1$ 的个数不超过在 ddm 序中的 $1$ 的个数。

暴力实现复杂度 $O(n^2)$ ，用数据结构优化即可做到 $O(n\log n)$ 。

期望得分： $20\sim 35$。结合算法一 、算法二期望得分 $75$。

算法四

我们来胡乱手玩一下。

在草稿纸上随便画一棵树，标一个从左到右的 ddm 序，随便交换一下，然后看自己能否构造出原来 ddm 序交换过来的方法。

无从下手？那就从最左边的叶子开始吧。

我们希望直接把最左边的叶子的 $a$ 得到，所以操作空间很小，只能把祖先里的某一个 $b$ 拉过来。

这时候就会发现，好像我不管怎么交换，也换不出除了祖先的 $b$ 以外的值啊？

随便证明一下：这里是叶子，所以这个位置的 $b$ 在交换过程中单调不增，也就只能变成祖先的 $b$。

我们当然也不希望有无用的交换，所以把某个祖先的 $b$ 拉过来之后仍然保持祖先的 $b$ 有序。发现现在把这个叶子直接删去也不会出什么问题了？

于是就得到一个构造交换顺序的方法：设 $lo{w}_x$ 为 $x$ 子树中 ddm 序的最大值，把所有点按 $low$ 从小到大排序，相同的点按深度从大到小排序，然后一个一个做。每次做的时候把祖先的一个 $b$ 拉下来，拉的过程中仍然保持祖先的 $b$ 有序。

仔细分析一下这个构造方法什么时候能构造出解。发现只要对于每个 $x$ 有 $lo{w}_x\ge a_x$ ，就一定能构造出来！

而因为子树内的最大值单调不增，所以 $lo{w}_x<a_x$ 时必定无解！

于是发现一个 ddm 序合法，当且仅当 $lo{w}_x\ge a_x$ 。这也可以用来证明算法三的正确性。（也许算法三能够用某种方法推到这个结论？）

那么唯一的问题就是怎么构造一个合法的 ddm 序了。

考虑 DP ：设 $d{p}_x$ 表示 $x$ 的 ddm 序至少是多少，才能保证子树内全部合法。显然应该按照 $dp$ 值从小到大的顺序遍历 $x$ 的儿子，所以很容易转移。

最后判断 $d{p}_1$ 是否等于 $1$ 即可。

复杂度 $O(n\log n)$ ，期望得分：$100$。

获奖名单

from matthew99，标程 by matthew99，数据，题解 by mayaohua

算法一

由于长度为 $2$ 的串可以翻转，我们不区分原串和翻转后的串。

考虑先全排列暴力枚举 $p$，得到字符串的顺序。接下来我们需要寻找一个合法的 $q$，考虑从两边往内推逐个确定每位字符，注意到如果当前位置两边至少有一个字符已知，那么能继续推下去，否则可以发现除了两个相同的串外，下一步的方式至多只有一种，而两个相同的串只要不同向即可。

时间复杂度为 $O(n!\cdot n)$，期望得分 $15$ 分。

算法二

考虑扩展算法一的思路，同样从两边交替往中间推，这只需要记录一下当前已经用过的串和当前可能多出来的一个字符，可以用状压 DP 实现。

时间复杂度为 $O(2^n\cdot nm)$，期望得分 $35$ 分。

算法三

对于 $l_i=2$ 的数据，显然只需要把相同的串不同向对称放就好，但注意有个特殊情况：如果有奇数个串，正中间可以放一个形如 $11$ 的。

时间复杂度为 $O(n)$，期望得分 $10$ 分。

算法四

考虑算法一中的确定过程，不难发现除了最后中间的一段以外，我们在两边反复做匹配两个串的过程，即我们构造了两个相同的字符串。注意到这样的一个段，要么是两个长度为 $2$ 的相同串，要么是由长度为 $1$ 的串开始，然后交替扩展直到遇到另一个长度为 $1$ 的串。例如，给定串集合 $\{1,12,23,34,4\}$，我们可以构造出 $1234$ 和 $1234$。

由于字符串长度不超过 $2$，我们考虑这样一个建图：建立 $m+1$ 个节点，其中节点 $0$ 为源点，节点 $1\sim m$ 代表 $m$ 个字符，对每个长度为 $1$ 的字符串 $a$，我们连边 $(0,a)$，对每个长度为 $2$ 的字符串 $ab$，我们连边 $(a,b)$。那么发现每个算法一中交替扩展得到的段，对应一条恰好经过 $0$ 一次的边不重复回路。

对于 $L$ 为偶数的数据，答案回文串可能是由两个相同串其中一个翻转后拼起来，也可能在中间有一个形如 $11$ 的串。对于前者，显然是由若干交替扩展得到的串和若干成对出现的长度为 $2$ 的串组成，在图上看，这就是一个包含 $0$ 的欧拉回路和若干出现偶数次的边，因此有解当且仅当 $0$ 所在连通块有欧拉回路（每个点度数为偶数），且其它连通块每条边出过偶数次（包括自环）。对于后者，我们可以选择一个其它连通块的自环放在中间，这只需找到出现奇数次的自环。

对于 $L$ 为奇数的数据，用类似的方法可以发现要求是 $0$ 所在连通块有欧拉道路（即恰有两个奇度点，显然其中一个是 $0$），而此时其它连通块只能每条边都出现偶数次，这时候构造的话就是中间放一条从另一个奇度点到 $0$ 且仅经过 $0$ 一次的路径，这对应一个长度为奇数的回文串，剩余部分构造和偶数类似。

时间复杂度为 $O(n+m)\sim O(n\log n+m)$，期望得分 $100$ 分，需要比较注意细节，如果写挂的话可能只有很低的分数。

Bonus：如果不允许翻转长度为 $2$ 的串，是否存在多项式复杂度算法或可证明 NP 完全性？

诡异操作

from skip2004，数据，标程，题解 by skip2004

为了方便，下文中的 $w=\log v$。

算法一

我们用线段树维护这个序列，每个点维护区间最大值与区间的按位或。 一个点最多会被除法改变 $w$ 次，每次改变后可能会有一些与的改变，最多 $w$ 次，因此最多改变次数是 $O(w^2)$，我们在线段树上搜索修改，复杂度毛估估是 $O(n{w}^2\log n)$。

算一算发现一个大包都过不去，但能过两个特殊性质包：$2,4$。

仔细分析，对于这两个包，可以发现线段树上锁定区间后的搜索过程，每个线段树节点都最多被搜索 $w$ 次。因此复杂度为 $O(nw+q\log n)$。

算法二

我们发现上述算法毫无前途，我们总得把一个修改打标记吧。

容易发现除法打标记还要算和，非常困难，于是我们对与这个操作打标记。与打标记还要算和，我们用经典的方法，开一个 $w$ 长度的数组记录：对于每一位这个区间有多少个数这一位是 $1$。此时线段树上这一个节点的标记下传，信息上传等操作复杂度变为 $O(w)$，总复杂度分析得 $O(n{w}^2+q\log n\ast w)$，看起来还是没救。

算法三

我们发现这个算法在搜索过程中，在靠近叶子处最消耗时间，而这些地方我们数组里数都不大，我们考虑进行优化。

我们把这个 $w$ 个数列成一个表格，每行 $\log len$ 个数表示每个数的二进制位。

此时我们发现，我们可以用 $\log len$ 个压位变量来存储这个表格的每一列。至于信息上传，我们可以模拟加法，时间复杂度 $O(\log len)$，对于打标记，我们发现是某些行的数清 $0$，也就是每列与上其标记，也可以 $O(\log len)$ 解决，算带权和也可以轻松解决。

我们再来分析一下复杂度，锁定区间部分复杂度 $O(q{\log }^{2}n)$，搜索过程就是 $\sum \log len\ast w$，其中 $\sum \log len$ 可以由递归式 $f(n)=2f(\frac{n}{2})+\log n$ 使用主定理得出为 $O(n)$，故总时间复杂度为 $O(nw+q{\log }^{2}n)$。

航天飞机调度

from Itst，数据，标程，题解 by Itst

算法一

读懂题意后可以发现图上总共只有 $q+2$ 个点有意义。两两询问出最短路，需要 $\frac{(q+2)(q+1)}{2}$ 次询问。因此在前三个子任务中可以暴力询问求出两两之间的最短路。（谢罪：之前这里算错了导致子任务三 $q$ 大了 $1$。）

接着只需要枚举一个长度为 $q$ 的 $01$ 序列表示每一次紧急事件发生时需要调度哪一架飞机到达对应机场，复杂度 $O(2^q)$，可以通过子任务 $1$ 获得 $10$ 分。

算法二

注意到紧急事件序列每个事件的决策只和两架飞机此时所在的机场编号相关，故考虑使用动态规划解决。

设 $f_{i,j,k}$ 表示前 $i$ 个客流紧张事件已经结束，此时一架飞机停留在机场 $j$，一架飞机停留在机场 $k$，满足该条件下的最大调度价值和。转移即枚举哪一架飞机移动到 $P_{i+1}$ 转移到 $f_{i+1,P_{i+1},j}$ 和 $f_{i+1,P_{i+1},k}$。

复杂度 $O(q^3)$，可以通过前两个子任务获得 $25$ 分。

算法三

对于上述动态规划，可以注意到处理完第 $i+1$ 个客流紧张事件后，后两维总是有一维等于 $P_{i+1}$。因此可以把这一个确定的维度压掉。

设 $f_{i,j}$ 表示前 $i$ 个客流紧张事件结束时一架飞机在 $P_i$ 另一架飞机在 $j$ 时的最大调度价值和。$f_{i,j}$ 有两个转移：一个是加上 $distance(P_i,P_{i+1})$ 转移到 $f_{i+1,j}$，另一个是加上 $distance(P_{i+1},j)$ 转移到 $f_{i+1,P_i}$。

复杂度 $O(q^2)$，可以通过前三个子任务获得 $40$ 分。

算法四

子任务四是留给大家玩玩乱搞的。实际上随机数据的强度非常非常的弱。

一个想法是考虑魔改上面的 DP，可以注意到除了 $f_{i+1,P_i}$ 以外其他部分的转移是全体加一个值。全体加可以滚动数组后打标记处理，所以只需要优化 $f_{i+1,P_i}$ 的转移。很容易得到一些贪心策略，如：

1. 选前 $60$ 大的 $f_{i,j}$ 转移；
2. 选 $f_{i,P_{i-j}}$ 转移，其中 $j\in [1,60]$。

实际上它们都可以通过随机数据可以获得 $10$ 分，结合算法三可以获得 $50$ 分。

算法五

为了后文描述方便，我们把编号区间扩充为 $[1,2n]$，其中编号 $n+i(1\le i\le n)$ 对应的机场与编号 $i$ 对应的机场一致。

引理：对于 $u\le v\le x\le y<u+n$，$distance(u,x)+distance(v,y)\ge distance(u,y)+distance(v,x)$

证明：注意到题目给出的图是平面图，同时编号按照顺时针顺序编号，且所有边都在多边形内部，因此 $distance(u,x)$ 对应的最短路径要么经过 $v$ 或 $y$，要么将多边形分成了两个部分，$v$ 和 $y$ 在不同的部分。这样 $distance(u,x)$ 与 $distance(v,y)$ 对应的两条路径必定有交点，不妨设交点为 $r$。则利用最短路的三角形不等式有

$$\begin{array}{rl}& distance(u,x)+distance(v,y)\\ =& distance(u,r)+distance(x,r)+distance(v,r)+distance(y,r)\\ =& (distance(u,r)+distance(y,r))+(distance(x,r)+distance(v,r))\\ \ge & distance(u,y)+distance(v,x)\end{array}$$

利用这个长得像四边形不等式的东西可以做什么呢？

考虑一个长度为 $q$ 的 $01$ 序列 $a_1,a_2,\cdots ,a_q$，$a_i$ 表示两架飞机中的哪一架飞到 $P_i$ 机场解决紧急事件。显然这样的每个序列对应着每一个调度方案。对于对应最优调度方案的序列，我们有定理：

定理：存在一个最优序列 $\{a_1,a_2,\cdots ,a_q\}$，对于 $i\in [1,q-1]$，若 $a_i=a_{i+1}$，则 $\mathrm{\forall }j\ge i+1,a_j=a_i$。

证明：对于一个最优序列，若 $\mathrm{\exists }j\ge i+1$ 满足 $a_j\ne a_i$，则一定是某一架飞机直接从 $P_i$ 调度到 $P_{i+1}$，另一架飞机直接从 $P_k$ 调度到 $P_j$，此时 $k<i<i+1<j$，即 $P_k\le P_i\le P_{i+1}\le P_j$。由引理有 $distance(P_k,P_{i+1})+distance(P_i,P_j)\ge distance(P_k,P_j)+distance(P_i,P_{i+1})$。故将序列中下标 $\ge i+1$ 的所有位置的值反转后可以得到一个不劣的方案。同时容易说明按照某种顺序不断进行翻转总是能得到一个满足定理条件的序列。

这也就说明最优序列一定满足：除了一段后缀都由一架飞机搞定以外，剩余部分一定是 $01$ 交替的。显然这样的序列只有 $O(q)$ 个，且在所有这样的序列中第 $i$ 个事件只会由 $P_{i-1}$ 或 $P_{i-2}$ 调度飞机。因此只需要 $2q$ 次询问，然后枚举后缀长度并动态维护价值和，取最大值即可。复杂度 $O(q)$，可以通过子任务 $5$，结合算法三、四可以获得 $75$ 分。

与此同时，这样的序列性质也说明了为什么把算法四的第二种 DP 乱搞做一些小小的修改即可通过本子任务。（真的不是数据水！）比赛开始一小时后就有选手 900B 怒拿 $75$ 我大为震撼！

算法六

注意到上面的引理是一个四边形不等式的性质，自然地想到使用决策单调性优化 DP。

最重要的问题是权值矩阵的设计。如果直接设计权值矩阵 $A=\{a_{i,j}=distance(i,j)\}$，其 DP 转移是不满足决策单调性的。因为使用决策单调性的权值矩阵要求 $\mathrm{\forall }u\le v,x\le y$ 都有 $a_{u,x}+a_{v,y}\ge a_{u,y}+a_{v,x}$，但是在没有约束 $x$ 与 $v$ 的大小关系的情况下引理并不成立。

解决办法是：在矩阵中填入若干 $-\mathrm{\infty }$ 使得 $\mathrm{\forall }u\le v,x\le y$ 的变量取值条件变为 $\mathrm{\forall }u\le v\le x\le y<u+n$ 的条件。

具体考虑 $n\times 2n$ 的权值矩阵 $W=\{w_{i,j}\}$，其中 $w_{i,j}$ 在 $j\in [i,i+n-1]$ 时取值为 $distance(i,j)$，否则为 $-\mathrm{\infty }$。可以发现此时在 $v>x$ 或 $y\ge u+n$ 的情况下 $a_{v,x}+a_{u,y}=-\mathrm{\infty }$，因此 $a_{u,x}+a_{v,y}\ge a_{u,y}+a_{v,x}$ 不等式总是成立。所以需要判断的只有 $\mathrm{\forall }u\le v\le x\le y<u+n$ 的情况，而利用引理不等式也是总是成立的。所以这个矩阵满足四边形不等式。

这样我们对 $f_{i,j}$ 数组的 $i$ 维度滚动数组并维护全体加法标记后，设 $f(y)=\underset{x=1}{\overset{n}{max}}{W}_{x,y}+f_x$，则 $f_{i+1,P_i}=max(f(P_{i+1}),f(P_{i+1}+n))$。

同时对于每个 $y$，设 $x_y$ 表示取到 $f(y)$ 的最小行编号 $x$，则 $f$ 固定的情况下 $x_y$ 是随着 $y$ 的增大单调不降的。这意味着我们可以对于 $f$ 直接维护 $x_1,x_2,\cdots ,x_{2n}$。其构成了至多 $n$ 个区间，使用 set 维护这些区间。

每一次产生 $f$ 数组的更新（也就是 $f_{i+1,P_i}=max(f(P_{i+1}),f(P_{i+1}+n))$）时，滚动数组中 $f_{P_i}$ 的值产生了变化且一定不会变小，因此其在 $x_1,x_2,\cdots ,x_{2n}$ 序列上会占据一段新的区间，且新占据的区间一定包含之前占据的区间。在 $x_1,x_2,\cdots ,x_{2n}$ 上二分出 $P_i$ 占据的区间的新的左端点和右端点即可。注意每一次遇到紧急事件，对于 DP 数组的其他部分都用打标记的方式更新了，所以每一次紧急事件都只需要更新一次该序列。

最终只需要约 $4q\log 2n+3q$ 次操作即可完成动态规划数组的更新与每次更新之后 $x_1,x_2,\cdots ,x_{2n}$ 的维护。可以通过子任务六获得 $75$ 分，结合算法五可以获得满分。