A. Acronym

枚举每个单词判断即可。

B. Baggage

考虑两个包裹分别从 $u$ 运到 $v$，中途没有同时运送两个包裹，则方案形如：

• 包裹 1 $u\to a_1$，空手 $a_1\to u$，包裹 2 $u\to b_1$，空手 $b_1\to a_1$，包裹 1 $a_1\to a_2$，空手 $a_2\to b_1$，包裹 2 $b_1\to b_2$，……，包裹 1 $a_k\to v$，空手 $v\to b_k$，包裹 2 $b_k\to v$。

可以发现这样的方案可以重新排列成：

• 包裹 1 $u\to a_1\to a_2\to\cdots\to a_k\to v$。
• 空手 $v\to b_k\to a_{k-1}\to b_{k-2}\to \cdots\to a_1\to u$。
• 包裹 2 $u\to b_1\to b_2\to\cdots\to b_k\to v$。

因此代价不小于 $2\mathrm{dis}_1(u,v)+\mathrm{dis}_0(v,u)$，其中 $\mathrm{dis}_c(x,y)$ 是从 $x$ 到 $y$，只能经过容量不少于 $c$ 的边的最短距离。

而 $2\mathrm{dis}_1(u,v)+\mathrm{dis}_0(v,u)$ 显然是一个合法方案，因此只需将 $u$ 到 $v$ 连上距离为 $2\mathrm{dis}_1(u,v)+\mathrm{dis}_0(v,u)$、容量为 $2$ 的边，然后求容量 等于 $2$ 的最短路即可。

时间复杂度 $O(n^3)$。

C. Cows

二分答案，转化为判定是否能够在 $x$ 分钟内吃完所有的草。

按照 $i$ 从小到大的顺序，维护如下的状态：考虑下标在 $[i,n]$ 中的牛，且满足下列状态之一

• 存在不超过 $2$ 个时间区间，牛 $i-1$ 会在这些时间区间内帮牛 $i$ 吃草。有两种情况：
  • 如果在时间 $t$ 吃完了所有了牛 $i$ 的所有草，则牛 $i$ 可以在 $[t,x]$ 时间内帮牛 $i+1$ 吃草。
  • 否则，设剩余的草的数量为 $a$，则牛 $i+1$ 需要在 $[x-a,x]$ 时间内帮牛 $i$ 吃草。
• 存在一个时间区间 $[l,r]$，牛 $i$ 需要帮牛 $i-1$ 吃草。有两种情况：
  • 如果牛 $i$ 自己能够在 $l$ 时间之前吃完所有草，设吃完草的时间为 $t$，则牛 $i$ 可以在 $[t,l]$ 和 $[r,x]$ 时间帮牛 $i+1$ 吃草。
  • 否则，设在 $l$ 时刻剩余的草的数量是 $a$，则牛 $i+1$ 需要在 $[l-a,l]$ 时间内帮牛 $i$ 吃草。

如果最终牛 $n$ 不能吃完所有的草则说明答案大于 $x$。

时间复杂度 $O(n\log H)$。

D. Diminishing Fractions

分数的分母显然不超过 $M=\mathrm{lcm}\{1,2,\ldots,n\}$，而分子最小是 $1$，因此可能的最小值是 $1/M$。我们考虑通分，在 $\bmod M$ 意义下构造 $1$，然后只需减去整数部分即可（因为已知分子是 $1$，可以直接用浮点数计算）。

设 $\le n$ 的所有极大素数幂分别为 $p_1^{e_1},p_2^{e_2},\ldots,p_k^{e_k}$，则 $M=\prod_{i=1}^k p_i^{e_i}$。现在我们想要找到 $a_i\in [0,p_i^{e_i})$ 满足 $\left(\sum_{i=1}^k a_i(M/p_i^{e_i})\right)\bmod M=1$。

这可以通过 CRT 构造：我们希望 $x\bmod p_i^{e_i}=1$，所以令 $a_i$ 为 $M/p_i^{e_i}$ 在模 $p_i^{e_i}$ 意义下的逆元即可。

因为 $\sum n$ 很大但 $N=\max n$ 不大，我们在每组数据中分别进行求逆，则只需按照 $n$ 从小到大的顺序维护 $\prod_{j\ne i}p_j^{e_j}\bmod p_i^{e_i}$。每次增加一个素数幂时，都可以在 $O(k)=O(n/\log n)$ 的时间内完成维护。

总时间复杂度 $O\left(\frac{N^2}{\log^2N}+\sum n\right)$。

E. Express Rotations

考虑一个指向序列开头的指针，初始在 $a_1$ 之前。这样操作可以转化为指针循环向前移动、循环向后移动和删除指针之后的第一个数。

考虑设 $\mathrm{dp}(v,i)$ 表示删除了所有 $\ge v$ 的数，指针的位置在 $i$ 的最小代价。我们可以认为只有需要删除一个数时需要移动指针，因此有用的状态一定满足 $a_i=v$，因此总状态数是 $O(n)$ 的。

从 $v+1$ 到 $v$ 的转移，首先从之前所有有用的位置转移到所有 $a_i=v$ 的位置，这只需要先转移到前后相邻两个位置，然后再正反分别扫两遍更新。计算从位置 $i$ 向后移动到位置 $j$ 的代价，也就是计算 $[i,j)$ 中所有 $\ge v$ 的数的总和，可以用树状数组在 $O(\log n)$ 时间内计算。

接下来考虑删除所有等于 $v$ 的数。可以发现指针的移动要么是先往前再往后，要么是先往后再往前。如果是先往前再往后，可以认为所有数都是在往后的过程中被删除，因此直接用指针移动的代价减去所有 $=v$ 的数的总和来更新即可。如果是先往后再往前，因为往后移动的过程中，删除一个数不需要代价，但往前移动的过程中需要先移动到数之前再删除，所以有 $v$ 的代价。我们可以将少的代价在往后移动的过程中计算，即从 $i$ 移动到 $j$ 的代价是 $[i,j)$ 中所有 $>v$ 的数的总和减去 $v$。这会导致一个问题：移动的代价可能是负数，导致一直在环上绕圈。这是因为，我们只有在第一次删除一个数的时候会带来总代价的减少，但直接在环上转移忽略了这个限制。一个解决方案是使用单调队列，限制只能往后移动 $\mathrm{cnt}_v-1$ 次。

时间复杂度 $O(n\log n)$。

F. Frogs

考虑计算 $p=n$ 的答案。令 $b_i=a_{i+1}-a_i$（下标都是 $\bmod n$ 意义下的），即青蛙 $i$ 要追的青蛙和它坐标的差。如果 $b_i\ge 0$，则青蛙 $i$ 会向右跳，否则会向左跳。考虑 $b_i$ 的变化，当 $b_i\ge 0$ 且 $b_{i+1}< 0$ 时会减去 $2k$，当 $b_i< 0$ 且 $b_{i+1}\ge 0$ 时会加上 $2k$。可以发现，在有限轮之后，所有的 $b_i$ 都会落入 $[-2k,2k)$ 内。此后 $\{b_i\}$ 一定会进入一个循环，我们希望判断在一个循环内，青蛙的坐标是否不变。注意到当所有 $b_i\in[-2k,2k)$ 时，$b_i$ 的符号（负数还是非负）只和上一个时刻 $b_{i+1}$ 的符号有关，因此在循环中负数的个数是始终不变的，因此我们只需判断负数的个数是否等于非负数的个数。

我们只需判断是否有 $n/2=\sum[b_i< 0]=\frac{1}{2k}\sum(b_i\bmod 2k-b_i)$。注意到 $\sum b_i=0$，而 $\sum (b_i\bmod 2k)$ 是常数，因此只需判断是否有 $\sum(b_i\bmod 2k)=\sum((a_{i+1}-a_i)\bmod 2k)=nk$ 即可。

对于所有的 $p$ 计算答案，也只需要在 $p$ 增大的时候维护这个和。

时间复杂度 $O(n)$。

G. Game MPO

将所有的 M 和 P、O 和 O 连边，则只需从所有大写字母开始 BFS 即可得到最终状态。

H. High Jump

最优策略可以表示成 $a_1< a_2<\cdots< a_k$，依次挑战高度 $a_1,a_2,\ldots,a_k$。分数的期望是 $p_{a_1}a_1+p_{a_1}p_{a_2}(a_2-a_1)+p_{a_1}p_{a_2}p_{a_3}(a_3-a_2)+\cdots$。令 $a_0=0$，这个式子也可以写成 $f(i)=(f(i+1)+(a_{i+1}-a_i))p_{a_{i+1}}$，答案即为 $f(0)$。

考虑从后往前 DP，则 $\mathrm{dp}(i)=\max_{j>i}\{(\mathrm{dp}(j)+j-i)\cdot p_j\}$，可以用凸包优化转移。

时间复杂度 $O(n)$。

I. Imbalanced Teams

显然最大值等于前 $k$ 大的和减去前 $k$ 小的和。在确定了选择的数的可重集后，只需乘上对应的组合数即可。注意如果两个队伍有相同的数，还需要计算分组的方案数，并且当所有数全相等时，两组是本质相同的，方案数需要除以 $2$。

时间复杂度 $O(n)$。

J. Just Zeros

考虑维护 $f(S)$ 表示翻转的行的集合是 $S$ 的情况下，还需要多少步能够将所有数变成 $0$。也就是翻转行后，每一列的 $\min\{c,1+h-c\}$ 之和。通过 $f(S)$ 可以在 $O(2^h)$ 时间内计算答案。

如何在操作后维护 $f(S)$：

• P 和 K 操作都只会影响一列，可以对每个 $S$ 重新计算该列的贡献。
• R 操作只需将 $f(S)$ 和 $f(S\oplus \{i\})$ 交换。注意需要打一个第 $i$ 行取反的标记，在另外两种操作中需要用到。

时间复杂度 $O((w+q)2^h)$。

K. Kindergarten Square

通过两行的差可以求出 $w$，而 $h$ 越大越好，然后判断是否满足条件即可。

L. Looping RPS

考虑对 $s_i^\infty$ 建立 Trie，则三个人形成一个环当且仅当它们在同一个点的三个不同子树内。因此建立 Trie 后可以直接枚举 LCA 计算贡献。

建立 Trie 分为两步：排序，然后计算相邻串的 LCP 并建立笛卡尔树。

难点主要在于排序，直接按照 $a+b< b+a$ 比较可能导致时间复杂度变为 $\Omega(n|s|)$。我们希望比较两个串的复杂度是 $O(\min\{|a|,|b|\})$，则总复杂度为 $O(\sum|s_i|\log n)$。不妨设 $|a|\le |b|$。如果 $a$ 不是 $b$ 的前缀则可以直接比较，否则我们需要求 $b$ 和 $b[|a|:]$ 的 LCP，这可以通过预处理每个串的 Z 函数后 $O(1)$ 得到。

时间复杂度 $O(\sum |s_i|\log n)$。

A. Arrow a Row

一个串能通过操作得到的必要条件包括：

• 以 > 开头。
• 以 >>> 结尾
• 至少有一个 -。

而事实上上述条件也是充分的。如下是一个可能的构造：

• 当目标串不以 ->>> 结尾时，重复操作 $(n-4,5)$，这样可以视作删除了最后一个字符。最终目标串一定是以 ->>> 结尾。
• 枚举 $i$ 从 $1$ 到 $n-4$，如果 $s_i$ 为 - 则不操作，否则令 $j$ 为 $i$ 之后第一段连续的 - 的结尾位置，操作 $(i,j-i+4)$。

操作次数显然不超过 $n$，时间复杂度也为 $O(n)$。

B. Athlete Welcome Ceremony

先求出有 $x$ 个 a、$y$ 个 b、$z$ 个 c 的好序列，然后做一个三维前缀和，即可在 $O(1)$ 时间内回答询问。

令 $\mathrm{dp}(x,y,z,\mathrm{ch})$ 表示有 $x$ 和 a、$y$ 个 b、$z$ 个 c，且以 $\mathrm{ch}$ 结尾的好的前缀个数。因为前缀长度就是 $x+y+z$，枚举下一个字符即可 $O(1)$ 转移。

时间复杂度 $O(n^3+Q)$。

C. Chinese Chess

对状态集合（状态为 (位置，类型)）进行搜索，枚举询问的格点，然后根据距离分成若干个子集。实现后可以发现，即使对于全部位置都可行的情况，也只需要 $3$ 步即可确定类型。因此总的搜索节点数不超过 $90^3$，如果速度还是很慢，可以考虑打表 $3$ 步的所有决策，这样只需要搜索 $2$ 步以内的情况。搜索的时候可以顺便记录每个状态的决策。

实现时注意每种棋子的移动方式。

D. Closest Derangement

注意到当 $p_i\ne i$ 时，$\sum_{i=1}^{n}|p_i-i|\ge n$。

当 $n$ 是偶数时，最小值可以取到 $n$，且只在排列 $2,1,4,3,\ldots,n-1$ 取到。

当 $n$ 是奇数时，根据奇偶性，最小值为 $n+1$。可以在排列 $\ldots,2k+2,2k+3,2k+1,\ldots$ 和 $\ldots,2k+3,2k+1,2k+2,\ldots$ 取到（前后的部分和偶数时一样，相邻数两两对换）。这样的排列共 $n-1$ 个，现在我们要找到 $p_{q_1},p_{q_2},\ldots,p_{q_n}$ 的字典序第 $k$ 小，只需快速实现比较两个排列，然后调用 nth_element 即可。

比较两个排列 $p_1,p_2$ 只需找到最小的 $i$ 使得 $p_{1,q_i}\ne p_{2,q_i}$。注意到对于任意两个不同的好的排列，对应不同的位置一定是一个区间加上边界的 $O(1)$ 个零散点，只需在 $q^{-1}$ 上 RMQ，然后暴力统计零散点即可。

时间复杂度 $O(n\log n)$ 或 $O(n)$。

E. Disrupting Communications

要求的是和 $u$ 到 $v$ 的路径相交的连通块数。考虑用总的连通块数减去和 $u$ 到 $v$ 的路径不相交的连通块数。

令 $l=\mathrm{LCA}(u,v)$，则和 $u$ 到 $v$ 的路径不相交的连通块有以下两种：

• 完全在 $l$ 的子树外部。
• 完全在 $l$ 的子树内部，且连通块的根不在 $u$ 到 $v$ 的路径上。

令 $f(x),g(x)$ 分别表示以 $x$ 为根的连通块数和 $x$ 子树内的连通块数，则转移如下： $$f(x)=\prod_{y\in \mathrm{ch}(x)}(1+f(y))\\ g(x)=f(x)+\prod_{y\in \mathrm{ch}(x)}g(y)$$ 同理，令 $f_o(x),g_o(x)$ 表示删除 $x$ 的子树，且以 $x$ 的父亲为根的树对应的答案。注意这里计算 $f_o(x)$ 不能使用除法（可能会有除以 $0$ 情况），而应该预处理前后缀乘积。

再令 $\mathrm{sum}_f(x)$ 为 $x$ 到根的路径上的所有点 $y$ 的 $f(y)$ 的和，则答案为 $$g(1)-g_o(l)-g(l)+\mathrm{sum}_f(u)+\mathrm{sum}_f(v)-2\mathrm{sum}_f(l)+f(l)$$ 时间复杂度 $O(n+q\log n)$。

F. Double 11

对于一个分组方案，设每组的个数和总和分别为 $c_i$ 和 $s_i$。要在 $\sum_{i=1}^mk_i\cdot s_i\le 1$ 的前提下最小化 $\sum_{i=1}^m \frac{c_i}{k_i}$，一定有每组的 $\frac{\mathrm{d}(c_i/k_i)}{\mathrm{d}(k_i\cdot s_i)}$ 是相等的，即 $k_i$ 正比于 $\sqrt{\frac{c_i}{s_i}}$。令 $S=\sum_{i=1}^m \sqrt{c_is_i}$，则 $k_i=\frac{\sqrt{c_i/s_i}}{S}$，$\sum_{i=1}^m \frac{c_i}{k_i}=\sum_{i=1}^m \sqrt{c_i s_i}S=S^2$。因此题目所求的答案就是 $S$。

注意到确定每个分组的大小之后，每个系数 $\sqrt{c_i}$ 就确定了，因此一定是把较小的数分到较大的组。因此我们可以将数组排序，从而每一组一定是一个区间。

考虑排序后的三个区间 $(c_1,s_1),(c_2,s_2),(c_3,s_3)$（$s_1/c_1\le s_2/c_2\le s_3/c_3$）。事实上我们有如下不等式： $$\sqrt{(c_1+c_2+c_3)(s_1+s_2+s_3)}+\sqrt{c_2s_2}\ge \sqrt{(c_1+c_2)(s_1+s_2)}+\sqrt{(c_2+c_3)(s_2+s_3)}$$ 一个证明如下：

• 移项，变为 $\sqrt{(c_1+c_2+c_3)(s_1+s_2+s_3)}-\sqrt{(c_1+c_2)(s_1+s_2)}\ge \sqrt{(c_2+c_3)(s_2+s_3)}-\sqrt{c_2s_2}$。
• 令 $c_1\gets c_1+c_2,s_1\gets s_1+s_2$，这不会改变作为前提的不等关系，只需证 $\sqrt{(c_1+c_3)(s_1+s_3)}-\sqrt{c_1s_1}\ge \sqrt{(c_2+c_3)(s_2+s_3)}-\sqrt{c_2s_2}$。
• 令 $a_i=s_i/c_i$，$f_i(x)=\frac{\partial\sqrt{(c_i+x)(s_i+a_3x)}}{\partial x}=\frac{a_3(1+2x)+a_i}{2\sqrt{(1+x)(a_i+a_3x)}}$，则上述不等式等价于 $\int_0^{c_3}f_1(x)\mathrm{d}x\ge \int_0^{c_3}f_2(x)\mathrm{d}x$，只需证明对任意 $x\ge 0$ 都有 $f_1(x)\ge f_2(x)$。再次求导会发现 $\frac{\partial f_i(x)}{\partial a_i}$ 在 $(0,a_3)$ 上恒为负，因此命题得证。

因此转移函数是 Monge 的，可以用 WQS 二分 + 决策单调栈在 $O(n\log n\log\epsilon^{-1})$ 的时间内求解。二分时需要注意精度问题，应当需要 long double。

G. Expanding Array

考虑序列中相邻的两个数 $x,y$。首先通过插入两个数的 XOR 可以得到序列 $x,y,x\oplus y,x,y$，也就是可以无限复制一对相邻的数，使得操作时不会将其消耗掉，因此我们可以把操作看成选中一对数 $(x,y)$，将 $(x,x\operatorname{op}y)$ 和 $(x\operatorname{op}y,y)$ 加入可能的相邻数的集合。不断重复这样的操作，最后就能得到所有可能出现的相邻数对，自然就能算出可能出现的不同数的个数。

接下来分析一下这样的数对的个数，序列中本身有 $n-1$ 对相邻的数，可以看作是独立的。对于相邻的两个数 $x,y$，因为进行的都是位运算，所以运算得到的任何一个数都可以看作两个位的一个函数 $f(x,y)$，其中 $x,y,f(x,y)\in\{0,1\}$，且 $f(0,0)=0$，因此至多有 $2^3=8$ 种可能。数对的数量自然不会超过 $8^2\cdot n$。事实上，打表可以发现这 $8$ 种可能的数都是可以产生的，因此直接枚举然后去重即可。

时间复杂度 $O(n)$ 或 $O(n\log n)$。

H. Friendship is Magic

先考虑如何计算一个 $f(x)$。当分割点向右移时，显然左侧单调递增，右侧单调递减。考虑找到最后一个左侧小于右侧的位置。即把 $x$ 划分为 $l,m,r$，其中 $m$ 是一个数位，满足 $10l+m\ge r$ 且 $l < m\cdot 10^{|r|}+r$，则 $f(x)=\min\{10l+m-r,m\cdot 10^{|r|}+r-l\}$。

现在考虑求 $f(x)$ 的和，枚举 $m,|r|$，然后枚举 $f(x)$ 取哪边，例如取 $10l+m-r$，则有限制 $$0\le l\le L\\ 0\le r\le R\\ 10l+m\ge r\\ l < m\cdot 10^{|r|}+r\\ 10l+m-r\le m\cdot 10^{|r|}+r-l$$ 把 $(l,r)$ 放到平面上，则这些限制都是半平面，且斜率只有 $0,\infty,10,1,\frac{11}{2}$ 这几种，通过分类讨论可以求出半平面交中所有点的 $l,r$ 之和，进而计算出答案。也可以直接枚举 $l$ 的奇偶性，使得斜率都是整数，然后找到半平面的所有交点并分段，每一段中固定 $l$ 的答案都是关于 $l$ 的二次函数，进而通过插值求总和。

时间复杂度 $O(|\Sigma|\cdot \log _{|\Sigma|}n)$，其中 $|\Sigma|=10$，且常数较大，需要精细实现。

I. Good Partitions

$k$ 是好的当且仅当对于任意 $i=1,2,\ldots,n-1$，如果 $i$ 不是 $k$ 的倍数，则 $a_{i+1}\ge a_i$。

也就是说，令所有满足 $a_{i+1}< a_i$ 的 $i$ 的 GCD 为 $d$，如果 $d=0$ 则 $k=1,2,\ldots,n$ 都是好的，否则只有 $d$ 的因子是好的。

单点修改会导致一些 $i$ 被插入或删除，可以使用线段树维护 GCD，并且预处理每个数的因子个数来快速回答询问。

时间复杂度 $O((n+q)\log n)$。

J. Grand Prix of Ballance

按照题意模拟即可。注意忽略掉非当轮比赛和消息和每位选手第二条及以后的消息。

时间复杂度 $O(n+m\log m+q)$。

K. Magical Set

令 $\Omega(x)$ 表示 $x$ 的质因子数量（计算重数）。设初始集合为 $S$，结束集合为 $T$，则总的操作次数不会超过 $$\sum_ {x\in S}\Omega(x)-\sum_{x\in T}\Omega(x)$$ 而只要每次恰好除掉一个质因子，这个上界就是能够达到的。而事实上，只要 $S$ 和 $T$ 存在一个完美匹配（$x\in S$ 匹配 $y\in T$ 当且仅当 $y\mid x$），就一定存在达到这个上界的操作序列。具体来说，我们可以通过如下方法构造这个操作序列：

• 对于 $x\in S$，设 $M(x)$ 是完美匹配中和 $x$ 匹配的 $T$ 中的数。如果对于任意 $x\in S$，$M(x)=x$，则构造完成。否则找到 $M(x)\ne x$ 的最小的 $x$，令 $p$ 为 $x/M(x)$ 的任意一个质因子，然后重复以下过程：

  • 如果 $x/p\notin S$，则将 $x$ 变为 $x/p$，这就完成了一次操作。

  • 如果 $x/p\in S$，则说明 $M(x/p)=x/p$ 且 $M(x)\ne x/p$，我们可以交换 $M(x)$ 和 $M(x/p)$，然后令 $x/p$ 成为我们考虑的 $x$，重复这个过程。

    由于这个过程中 $x$ 不断变小，因此一定会终止。

因此，问题变成了为 $S$ 中的每个数 $x$ 选择一个因子 $y$，使得这些因子互不相同，且最小化它们的 $\Omega(y)$ 的和。我们找到每个数的所有因子，如果因子超过 $n$ 个，我们事实上只需要保留 $\Omega(y)$ 最小的 $n$ 个（即使有 $n-1$ 个被其他数选择，还会剩下一个），然后在 $x_S$ 和 $y_T$ 之间连一条边。

最终我们形成了一个左部 $n$ 个点，右部不超过 $n^2$ 个点，不超过 $n^2$ 条边的二分图，要找一个左部完美匹配，使得右部选择的点的 $\Omega(y)$ 之和最小。可以将右部的所有点按照 $\Omega(y)$ 从小到大排列，然后用匈牙利算法寻找匹配。这个算法的正确性来自于拟阵。而只要在未找到匹配时，不初始化算法中的 vis 数组，算法的复杂度就是 $O(|M|\cdot |E|)$，其中 $|M|$ 是匹配大小，$|E|$ 是边数。

时间复杂度 $O(n\sqrt {A}+n^3)$。

L. Recover Statistics

只需构造 $n=100$ 个数，前 $50$ 个数为 $a$，第 $51$ 到 $95$ 个数为 $b$，第 $96$ 到 $99$ 个数为 $c$，第 $100$ 个数为 $c+1$ 即可。

M. Two Convex Holes

注意到多边形的投影实际上只是多边形进行了平移和缩放，进行一些坐标变换后可以转化为两个多边形分别做匀速直线运动。进一步可以转化成多边形 $P_2$ 的速度为 $0$，$P_1$ 的速度为 $(0,1)$。

我们可以将多边形的面积以所有顶点的 $x$ 坐标分成 $O(n)$ 段，则每一段中多边形的上下边界都是线段。进一步容斥成 $($上边界 $-$ 下边界$)$，则只需要计算形如 $\min\{ax+b+t,cx+d\}$ 的函数的积分。这个函数可以按照 $t$ 分成三段，每段都是二次函数。因此面积可以表示成 $O(n)$ 段的分段函数，每一段都是二次函数。再预处理一下每一段的前缀和，询问时只需二分出端点所在的段，然后加上边界部分即可。

时间复杂度 $O((n+q)\log n)$。

A. Italian Cuisine

假设最后切的块是 $p_i$ 到 $p_j$，其中菠萝在直线 $p_ip_j$ 的左侧。

枚举 $i$，则 $j$ 应该在满足菠萝在直线 $p_ip_j$ 左侧的前提下尽可能大（我们认为 $p_{n+i}=p_i$，所以始终有 $j> i$）。这个 $j$ 要满足的条件具有单调性，并且当 $i$ 增大时，最大的 $j$ 也不降，所以可以用双指针维护这个过程。

算面积时只需求每条边的叉积的和。

时间复杂度 $O(n)$。

B. Generated String

考虑如果给的都是直接的串而不是一些子串的拼接怎么做。对所有串建立 Trie，则 $s$ 是 $t$ 的前缀当且仅当 $t$ 在 $s$ 的子树中，在 DFS 序上就是 $t$ 在一个区间内。对反串建立 Trie 就可以解决后缀。因此询问给定前缀后缀的串的个数实际上就是一个二维偏序，加上时间维度之后就是三维偏序，可以在 $O(n\log^2 n)$ 时间内解决。

现在变成给一个子串的拼接，唯一的区别就是没法直接建 Trie。只要我们能够把 Trie 建出来，后面的做法没有区别。事实上建立 Trie 也并不复杂，只需要将所有串按字典序排列，然后求出相邻两个的 LCP 长度，然后类似建虚树的方法，就能建出这些串的压缩 Trie。注意这里排序的时候，如果只是用后缀数组求 LCP 跳过一段，比较复杂度是 $O(k+l)$，其中 $k,l$ 分别是两个字符串的段数，则复杂度仍然可能达到 $\Omega (n^2)$。一个解决方法是，使用归并排序，并且递归过程中也计算相邻串的 LCP，然后在归并的过程中，利用已经计算的 LCP 避免重新从头开始比较。另一个解决方法是按照段数从小到大插入排序。在预处理后缀数组，支持 $O(1)$ 求 LCP 的前提下，两种方法的复杂度都是 $O(\sum k_i \log n)$。

总时间复杂度 $O(n\log n+q\log ^2q+\sum k_i\log q)$。

C. Permutation

考虑分治，每次将数列分成两半，然后确定每个数在哪一半。之后递归处理两个区间。

由于这道题的交互器是非适应性的，即排列是预先确定的，所以可以采用随机化。考虑将所有数 shuffle，然后每次询问两个数 $x,y$，前一半是 $x$，后一半是 $y$（区间以外的部分随便用 $x$ 或 $y$ 填充，不会有贡献）。答案有三种可能：

• 答案是 $0$，说明 $x$ 在后一半，$y$ 在前一半。
• 答案是 $1$，说明 $x,y$ 在同一侧，但不知道是哪一侧。
• 答案是 $2$，说明 $x$ 在前一半，$y$ 在后一半。

对于答案是 $0,2$ 的情况，能够直接确定两个数。对于答案是 $1$ 的情况，可以删掉 $x,y$ 的其中一个，用另一个继续进行询问。

分析一下询问次数，因为排列随机，近似可以看成每个数均匀独立在左右之间随机。每次询问有 $1/2$ 的概率确定 $2$ 个数，$1/2$ 的概率确定 $1$ 个数，因此每次期望确定 $3/2$ 个数，故期望询问次数约为 $2n/3$。

因此总的询问次数大约为 $\frac{2}{3}n\log n$。加上一些剪枝（例如当一侧已经满时不继续询问）后，实测 $n=1\,000$ 时大约需要 $6\,000$ 次询问。

D. Collect the Coins

二分答案，可以在线性时间内判断能否满足。

考虑按照时间从前往后，维护每个时刻，两个机器人可能的位置集合。事实上，一定可以表示成其中一个机器人在 $[l_1,r_1]$，另一个在 $[l_2,r_2]$（不区分两个机器人）。

初始时两个区间都是 $[1,10^9]$。对每个事件进行模拟：

• 当时间前进 $t$ 时，两个区间都往两侧扩展 $v\cdot t$。
• 当在位置 $c$ 出现一个硬币时：
  • 如果没有区间包含 $c$，则不可能。
  • 如果有一个区间包含 $c$，则对应区间变成 $[c,c]$。
  • 如果两个区间都包含 $c$，则任何一个机器人都可以收集硬币，而另一个机器人可能的位置是 $[l_1,r_1]\cup [l_2,r_2]$。因为两个区间有交，因此结果还是一个区间。

时间复杂度 $O(n\log C)$。

E. Normal Friends

不妨设线段树大小为 $n+1$，且根的分割点为 $n$。这样做的好处是，对于区间 $[1,x]$ 的翻转操作等价于找到 DFS 序第 $x+1$ 个叶子，然后将其到根的路径上的所有左子树整体翻转（最高的变到最低的，依此类推），并且内部所有左右儿子交换。

这样的操作实际上可以用 LCT 来完成。首先考虑怎么找到这条链，分成两步，分别是找到 DFS 第 $x+1$ 个叶子和对其进行 access 操作。

第一步需要在每条实链上用 splay 额外维护所有点的左/右子树（按照深度），以及哪些点有左/右儿子（当然是通过维护子树内有多少个点有左/右儿子）。这里我们假设每条实链的底端都是叶子。找 DFS 第 $k$ 个叶子的步骤如下：

• 令 $L=$ (所有左子树中叶子个数的和)。
• 如果 $k\le L$，则在所有左子树中找到第 $L$ 个叶子所在的子树，然后递归。
• 如果 $k=L+1$，则第 $k$ 个叶子就是这条链的底端。
• 如果 $k>L+1$，则在所有右子树中找到（自底向上）第 $L$ 个叶子所在的子树，然后递归找其中的第 $k-L-1$ 个叶子。

找到叶子之后，我们需要进行 access 操作，具体步骤如下：

• 我们不对每条链记录它的父亲（因为之后会有翻转操作，父亲没法维护），而是在找叶子的过程中，记录经过的路径，并且找到每条链切换时要接上的父亲。也就是找到链上第 $k'$ 个有左/右子树的结点。
• 自底向上，如果要把 $x$ 接上 $y$，首先要将 $y$ 和其目前的儿子 $z$ 断开。在这同时需要将左/右儿子同时分成两部分，对应断开之后的两条链，并把 $z$ 加入左/右儿子的列表（在这里更新 $z$ 的子树叶子数）。
• 将 $x$ 从 $y$ 所在链的左/右儿子列表中删除，将 $y$ 和 $x$ 所在链的左/右儿子列表拼接，并将 $x$ 接到 $y$ 上。

经过上面的两个步骤我们得到了一条链，询问的答案就是链的左子树的个数。下一步就是将链的左子树翻转，这又分成两个部分：

• 首先是将左儿子的列表整体翻转，这可以直接通过打翻转标记实现。
• 对每个左/右儿子，将其子树镜像，这对应着交换它所在链的左/右儿子列表，并且镜像它的所有左/右儿子，同时维护的信息（有多少个点有左/右子树）也需要交换。这里我们采用对链整体打标记，在找叶子的过程中处理标记。

注意翻转左儿子列表的操作会较大影响树的形态，但是 LCT 的 access 次数的分析并不会失效（每次操作只会影响 $O(\log n)$ 条轻边）。splay 的复杂度不再能沿用 LCT 的证明，但至少有上界 $O(\log n)$，总复杂度不超过 $O((n+q)\log ^2n)$，并且实际表现其实比较快。

F. Triangle

设三个串中字典序最大的为 $x$，其余两个为 $y,z$，则显然有 $xy>z$ 和 $xz>y$，因此只需要满足 $yz>x$ 或 $zy>x$。我们可以假设 $yz\ge zy$，这等价于 $y^\infty\ge z^\infty$，因此只是添加了一维偏序的限制。

现在要求 $yz>x$，而我们限制了 $y\le x$，因此 $y$ 一定是 $x$ 的一个前缀。我们可以枚举 $x,y$，总的枚举次数不会超过总串长。记 $x$ 去掉前缀 $y$ 后的串为 $y^{-1}x$，则 $z$ 只需要满足以下两个条件：

• $z^\infty\le y^\infty$。
• $x\ge z>y^{-1}x$。

对于后者，可以直接对所有串后缀排序。

对于前者我们需要将所有串按照这个规则排序。注意这里直接比较 $yz$ 和 $zy$ 的大小来排序，总的复杂度可以达到 $\Omega(n^2)$。一个复杂度正确的方法是，先判断两个串是否互为前缀，如果不是则可以直接比较，否则通过预处理的 $z$-函数/后缀数组，可以 $O(1)$ 求出 LCP 然后比较。这样单次比较复杂度是 $O(\min\{|y|,|z|\})$ 而不是 $O(|y|+|z|)$，总复杂度就是正确的 $O(\sum|S_i|\log n)$。

处理完这两个限制之后，就变成了二维偏序，可以在 $O(n\log n)$ 时间内解决。

需要注意的是，输入中会出现相同的串，所以我们需要记录每个串的出现次数，并且处理好三个串有相同的情况。

总时间复杂度 $O(\sum |S_i|\log n)$。

G. Stop the Castle 2

将问题转化为放 $m-k$ 个障碍，隔开尽可能多可以互相攻击的车。

只有在一行或者一列相邻的车才能互相攻击，这样的车只有 $O(n)$ 对。在它们之间的任意位置摆放障碍就能防止它们互相攻击。设有 $c$ 对能互相攻击的车之间能摆放障碍。

有的障碍可以阻挡两对车互相攻击（行列各一对），显然我们需要让这样的障碍尽可能多。假设我们能摆放 $x$ 个障碍，每个障碍都能阻挡互不相同的两对车，那么放 $m-k$ 个障碍就能阻挡 $\min\{c,m-k+\min\{m-k,x\}\}$ 对互相攻击的车。

把互相攻击的车看成点，如果一个障碍能阻挡两对车，就在对应的两个点之间连边，会形成一个二分图。$x$ 就是这张图的最大匹配。可以用 Dinic 算法或 Hopcroft-Karp 算法在 $O(m\sqrt n)$ 的时间中求解。

H. Intersection of Paths

如果 $k=1$，则所求的就是树的直径。当 $k$ 任意时，要求的其实就是只考虑两侧点数都不少于 $k$ 的边时树的直径。

注意所有询问互不相关，因此我们可以将询问按照 $k$ 从大到小的顺序重新排列。当 $k$ 减小时，会陆续加入边，这些边形成一个连通块，如果询问没有修改时，可以直接维护这个连通块的直径。当询问有修改

时有不同的做法，这里介绍其中的两个：

• 由于树的边权几乎不变，我们将询问中修改的边删除，分成两个连通块，分别求出两个连通块的直径，然后合并即可（整棵树的直径端点一定在这两条直径的端点中）。需要支持加点和求子树的直径，在按 DFS 序建立的线段树上合并直径即可。需要 $O(1)$ LCA。
• 直接使用修改边权的动态直径做法。直径等于在欧拉序上依次选 $3$ 个点（可以相同）$u,v,w$，$\mathrm{dep}_u-2\mathrm{dep}_v+\mathrm{dep}_w$ 的最大值。修改边权对欧拉序上深度的影响就是区间加。用线段树维护这个式子每一段的最大值即可。

时间复杂度 $O((n+q)\log n)$。

I. Find Yourself

首先注意到，任意的树都是能够确定的：

• 因为树是二分图，所以我们可以黑白染色，先确定怪物所在点的颜色，不妨设和根相同（否则走一步）。
• 假设怪物目前在 $x$ 的子树中且与 $x$ 颜色相同的一个结点（初始 $x$ 为根）。如果 $x$ 是叶子则游戏结束。否则，重复以下过程，直到 $x$ 只剩下一棵子树：
  • 询问 $x$，如果怪物在 $x$，那么游戏结束。否则，怪物只能走到 $x$ 的子树中，与 $x$ 颜色不同的结点。此时询问 $x$ 的一棵子树，如果怪物不在子树中，就可以删除这棵子树，否则可以删除所有其他子树。此时怪物又可能位于 $x$ 的子树中，未被删除的，和 $x$ 颜色相同的任意结点。
• 当只剩下一棵子树 $y$ 时，询问 $x$，如果怪物在 $x$，那么游戏结束。否则令 $x\gets y$，重复以上过程。

接下来考虑有环的情况。首先要注意到，如果图 $H$ 是不能确定的，则任意包含子图 $H$ 的图都是不能确定的。结合样例和打表观察，可以发现，以下的图都是不能确定的：

• 大小不为 $4$ 的环。
• 四元环，每个点都都和其他点有边。
• 四元环，相邻两个点分别连有长度为 $2$ 的链。
• 四元环，相邻三个点依次连有长度为 $2,1,2$ 的链。

此时可以看出，能确定的图的每一个点双都应该是四元环，或是多条长度为 $2$、起点终点相同的路径并起来的“纺锤”图。为了进一步地简化图的结构，我们还可以观察到如下性质：

• 如果存在两个二度点 $a,b$，它们的邻居相同，则可以删除其中的一个和其邻边，而不改变答案。
  • 证明：设原图为 $G$，$a,b$ 的邻居都是 $c,d$，删掉 $b$ 和其邻边之后的图为 $G'$。显然如果 $G$ 可以确定，则 $G'$ 可以确定。反过来，如果 $G'$ 可以确定，则使用相同的策略，可以在某一次询问后，确定怪物在 $a,b$ 其中的一个，然后怪物走一步之后只可能在 $c,d$，因此再询问一下 $c$ 即可确定怪物的位置。

经过上述变换之后，可以发现，能确定的图的每个点双都只能是四元环，且四元环不能有两个点都连有长度为 $2$ 的链，也不能四个点都和其他点有边。

事实上，上述必要条件也是充分的。

• 证明：满足上述条件的图，一定存在一个点，将这个点作为根时，每个四元环除了根以外的三个点中，至多有两个点连接了一个或多个叶子，另一个点没有和环外的点连边。设环上的点按顺序为 $a,b,c,d$，其中 $a$ 是根。我们可以先利用树的做法，将问题缩小到在 $a$ 的这个子树内确定怪物的位置。讨论两种情况：

  • $b,d$ 分别连有叶子 $b',d'$（可能多于一个）。先询问 $a$，如果不在 $a$，则下一步只可能在 $b,d$，再询问 $b$ 即可确定。

  • $b,c$ 分别连有叶子 $b',c'$（可能多于一个）。先询问 $a$，如果不在 $a$，则下一步只可能在 $b,d,c'$。再询问 $b$，如果不在 $b$，则下一步只可能在 $a,c$，再询问 $a$ 即可确定。

    因此满足上述条件的图都能够确定。

图的变换和判断上述条件都可以在 $O(n+m)$ 时间内完成，因此整个题可以在 $O(n+m)$ 时间内解决。

J. Sheriruth

如果一个点有两条出边 $u,v$，则 $u,v$ 会互相连边。如果 $u$ 或 $v$ 还有出边，会和 $u,v$ 整个连成一个团。以此类推，$u,v$ 可以到达的点都会形成一个团。不断合并这些团，最后整张图的每个连通块只有以下几种可能：

• 内向树。
• 内向基环树。
• 一个团，还有若干内向树，每棵树的根连向了团中的若干个点。

内向树的情况只需要判断祖先后代关系。内向基环树的情况还需要判断点在环上。

大小为 $s$ 的团的方案数就是 $\sum_{i=0}^{s-2}(s-2)^{\underline i}$。如果是从树根走到团上，要讨论走上来的点是否直接是 $v$，如果是则只有 $1$ 种方案。这个式子只需要对每个团单独计算，大小总和不超过 $n$。

总时间复杂度 $O((n+m+q)\log n)$，$\log n$ 在于排序和二分判断是否有某一条边，也可以做到线性。

K. Palindromic Polygon

首先将点复制一遍，变成 $2n$ 个点的序列。相当于可以选一个子序列 $i_1< i_2< \cdots< i_k$，要求 $i_k-i_1< n$，且 $f_{i_1},f_{i_2},\ldots,f_{i_k}$ 是回文序列，最大化凸包的面积。

考虑从两侧向中间 DP，设 $f(l,r)$ 是当前回文序列中对应位置是 $l,r$ 的最大面积。转移需要枚举 $i,j$，满足 $l< i\le j< r,f_i=f_j$，然后转移到 $f(i,j)$。这样做时间复杂度是 $O(n^4)$。

注意到如果 $(l,i)$ 和 $(j,r)$ 之间都有等于 $f_i$ 的点，那么把这两个点选上，面积一定不会变小（相当于凸包上多了两个三角形），因此有用的转移都满足 $i$ 是区间中第一个等于 $f_i$ 的点或 $j$ 是区间中最后一个等于 $f_i$ 的点。这样对于每个区间有用的转移减少到了 $O(r-l)$ 个，时间复杂度 $O(n^3)$。

L. Cosmic Travel

考虑查 $l=r$ 时如何查询。对所有 $a_i$ 建立 Trie，然后从根开始，如果 $l$ 的对应位为 $1$ 则交换了两棵子树，然后如果 $k\le$ (左子树大小)，递归左子树，否则递归右子树。

查询一个区间 $[l,r]$ 时，类似线段树的方式，按对应位分成两个区间，分别递归。我们只需要在 $[l,r]$ 恰好是一个完整的区间时快速回答。即对于每棵子树，对每个 $1\le k\le$ (子树大小)，预处理对 $j\in [0,2^d)$，$a_i\oplus j$ 的第 $k$ 小的和，其中 $d$ 是子树的位数。需要预处理的值，每个深度是 $O(n)$ 个，因此总共只有 $O(n\log C)$ 个。每个需要预处理的值都可以通过其孩子的值在 $O(1)$ 时间内得到。

总时间复杂度 $O((n+q)\log C)$。

M. The Quest for El Dorado

考虑 Dijkstra，将每个点的距离定义为 $(i,x)$，即最早在第 $i$ 轮才能到达，并且第 $i$ 轮至少走了 $x$ 的距离。显然我们希望 $i$ 尽可能小，并且 $i$ 相同的情况下 $x$ 尽可能小。

对于每条边 $(v,c,l)$，如果 $a_i=c$ 且 $x+l\le b_i$，那么新的距离是 $(i,x+l)$。

否则，我们需要找到最小的 $j>i$，满足 $a_j=c$ 且 $b_j\ge l$，新的距离就是 $(j,l)$。找这个 $j$ 可以用线段树或者二分 RMQ。

总时间复杂度 $O((n+m+k)\log (n+m+k))$。

A. An Easy Geometry Problem

令 $A_i'=A_i-i\cdot \frac{k}{2}$，则对于 $i$，$r$ 是好的半径当且仅当 $A'_{i+r}-A'_{i-r}=b$。

用线段树或树状数组维护正反两个方向的哈希值，询问时二分长度然后比较哈希值即可。

时间复杂度 $O(n+q\log^2n)$。

B. Counting Multisets

考虑 $p(S)$ 是奇数的条件，设 $\mathrm{cnt}(x)$ 是 $x$ 在 $S$ 中的出现次数，则 $p(S)=\frac{n!}{\prod_x \mathrm{cnt}(x)!}$。根据 Lucas 定理，$p(S)$ 是奇数当且仅当所有 $\mathrm{cnt}(x)$ 在二进制下相加没有进位。因此，合法的可重集就是对于 $n$ 的二进制中每个 $2^i$，任意选择一个 $x$ 重复 $2^i$ 次。

现在还要解决 $\mathrm{OR}_{x\in S}x=y$ 的条件。可以通过容斥将条件改写为 $\forall x\in S,\mathrm{bin}(x)\subset \mathrm{bin}(y)$（$x$ 的二进制中的 $1$ 是 $y$ 的子集）。

因此，对于固定的 $y$，只需要计算对于每个 $2^i\in \mathrm{bin}(n),2^j\in \mathrm{bin}(y)$，可以选或不选 $2^{i+j}$，总和等于 $x$ 的方案数。这可以通过数位 DP 解决，即 $f(i,j)$ 表示确定最低 $i$ 位，目前进位为 $j$ 的方案数，时间复杂度 $O(\log x\log n\cdot \mathrm{pcnt}(y))$。

总时间复杂度 $O(2^{\mathrm{pcnt}(y)}\mathrm{pcnt}(y)\log x\log n)$。

C. Counting Strings

（复读官方题解）

首先把条件改写成 $\gcd(r,r-l)=1$。建出 SAM，对于每个 $r-l$，假设保留所有 $\gcd(r,r-l)=1$ 的 $r$ 对应的结点，这样的串的个数就是这些结点到根的路径的并中深度为 $r-l$ 的点数。如果我们把这些结点按 DFS 序排序，则容易维护这些路径的并。

考虑通过搜索枚举 $r-l$ 包含质因子的集合来优化这个算法。在加入一个素数 $p$ 时，要删除所有 $p\mid r$ 的 $r$ 对应的结点，这样的删除对路径并的变化是删除一条链，可以用链表维护前驱后继，求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案，我们维护每个深度的点数，修改的影响是区间加，查询是单点求值，可以用 $O(1)$ 修改 $O(\sqrt n)$ 查询的分块维护。

接下来只需要分析这样搜索时需要修改的次数 $F(n)$。实测在 $n=10^5$ 时，修改的次数不超过 $2\cdot 10^7$。具体的分析是，修改次数等于 $\sum_{x=1}^{n-1}[\mu(x)\ne 0]\frac{n}{\mathrm{maxp}(x)}$，其中 $\mathrm{maxp}(x)$ 是 $x$ 的最大素因子。

时间复杂度 $O(F(n)+n\sqrt n)$。

D. Bracket Sequence

考虑 DP 计算一个给定字符串 $s$ 的方案数。$f(i,j)$ 表示 $S[0:i]$ 中等于 $\mathbb{()}^\infty[0:j]$ 的子序列的方案数，则答案就是 $f(|s|,2k)$。

令 $K=\max \{k\}$。对于第 $1$ 类区间询问，我们可以把这个 DP 写成 $v\cdot M_lM_{l+1}\cdots M_r$，其中 $M_i$ 是 $s_i$ 的转移矩阵。由于矩阵的特殊性质，可以在 $O(K^2)$ 的时间内计算一个矩阵乘上 $M_i$，因此只需要预处理 $M_1M_2\cdots M_i$ 和 $(M_1M_2\cdots M_i)^{-1}$，就可以在 $O(K)$ 时间内回答一个询问。

对于第 $2$ 类区间询问，首先可以添加一个 DP 状态，表示还没有进入子串，同时预处理 $M_1M_2\cdots M_i$ 的前缀和即可。

总时间复杂度 $O(nK^2+qK)$。

E. Dominating Point

令 $S(u)=\{v\mid (u,v)\in E\lor u=v\}$。点 $u$ 是支配点当且仅当不存在 $v\ne u$ 满足 $S(u)\subset S(v)$。

把所有点按度数从大到小排序，依次检查是否存在这样的 $v$。显然我们只需要检查已经确定是支配点的 $v$，而找到三个支配点后就可以直接返回，因此对于每个 $u$ 只需检查 $O(1)$ 个点，每次检查 $O(n)$。

总时间复杂度 $O(n^2)$。

F. An Easy Counting Problem

因为 $p$ 是素数，由 Lucas 定理可知组合数是 $p$ 进制下每一位组合数的乘积。$0\le b\le a< p$ 的组合数分布可以 $O(p^2)$ 暴力计算。

求出一位的组合数分布后，我们要计算其在 $i,j\to i\cdot j\bmod p$ 卷积意义下的 $k$ 次幂。通过找一个原根并将下标取离散对数的变换，我们可以将其转化为普通的循环卷积，可以用 FFT 优化。

时间复杂度 $O(p^2+p\log p\log k)$。

G. An Easy Math Problem

我们加上 $\gcd(p,q)=1$ 的限制，不同的 $(p,q)$ 就对应了不同的 $r$。考虑计算这样的 $(p,q)$ 的方案数。显然方案数是积性的，即每个素数独立，且 $p^k$ 的方案数是 $2k+1$（$(1,1),(p^i,1),(1,p^i)$）。分解 $n$ 之后直接计算即可。

可以预处理素数来加速分解，时间复杂度 $O(\sqrt N+q\frac{\sqrt N}{\log N})$。

H. Elimination Series Once More

我们对每个 $i$，和每个 $j=1,2,\ldots,n$，来计算 $i$ 能不能赢下第 $j$ 轮，也就是能不能让 $a_i$ 变成其所在的大小为 $2^j$ 的子树的最大值。

只需要判断两个条件：

• 所在子树中大于 $a_i$ 的不超过 $k$ 个。每次最多只能把一个换出去。
• $a_i\ge 2^j$。这是为了保证有足够多小的数放进子树。

这个条件可以在归并排序的过程中快速判断，时间复杂度 $O(n2^n)$。

I. Max GCD

我们枚举 $\gcd=d$，看是否能用 $d$ 的倍数满足条件。显然对于固定的 $j$，$i$ 应该越大越好，$k$ 在满足 $k-j\ge j-i$ 的前提下越小越好。

考虑从大到小枚举 $j$，找到对应的 $i$ 和 $k$。$i$ 可以直接找到，但 $k$ 并不单调。然而如果 $i$ 更小的时候 $k$ 更大，这样的三元组一定是不优的，因此仍然是只需要让 $k$ 单调下降。令 $A=\max\{a_i\}$，$d(A)$ 是 $1$ 到 $A$ 中约数个数的最大值，则可以在 $O(nd(A))$ 的时间中找到所有的三元组。

询问就是简单的二维偏序，为了平衡复杂度，可以使用 $O(1)$ 修改、$O(\sqrt n)$ 查询的分块，总时间复杂度 $O(nd(A)+q\sqrt n)$。

J. Graph Changing

考虑在 $G_1$ 中，两点有边当且仅当 $|u,v|\ge k$，如果 $u,v$ 可达，则最短路径长度一定不超过 $3$（$u\to 1\to n\to v$）。因此如果 $k>3$，$G_2$ 开始就是空图。

当 $k=3$ 时，显然当 $n$ 足够大时 $G_2$ 开始也是空图。

当 $k=2$ 时，显然当 $n$ 足够大时 $G_{i+1}$ 是 $G_i$ 的反图。

当 $k=1$ 时，显然 $G_1$ 开始就是完全图。

因此只需要预处理 $n$ 小的情况（例如 $n< 10$），特判 $k=1,2,3$，剩余的情况分类讨论答案是 $1,2,3$ 即可。

K. Penguins in Refrigerator

先求方案数，考虑从大到小插入数。首先大于 $M/2$ 的数相对顺序不改变，对于不超过 $M/2$ 的每个数 $a_i$，找到左右第一个大于 $M-a_i$ 的数，则 $a_i$ 只能插入到这个区间中。注意到这些区间形成一棵树形结构，因此方案数就是每个数插入的方案数相乘。

再求字典序最小的方案数。大于 $M/2$ 的数相对顺序不改变，可以连一条链。对于不超过，对于不超过 $M/2$ 的每个数 $a_i$，找到左右第一个大于 $M-a_i$ 的数，只需要它们之间的相对顺序不改变即可（因为其他的顺序关系都通过链确定了）。之后用堆维护，求字典序最小的拓扑排序即可。

时间复杂度 $O(n\log n)$。

L. Prism Palace

所求的就是随机旋转一个角度，有一条边在 $y$ 轴上的投影是整个凸包的概率。对于相邻的两个内角 $a,b$，这条边满足条件的角度范围是 $\max\{0,\pi-a-b\}$。对这些角度求和然后除以 $2\pi$ 即可。时间复杂度 $O(n)$。

M. Random Variables

考虑对每个 $k$ 计算每种数出现次数不超过 $k$ 的方案数。其等于 $$n![x^n]\left(\sum_{i=0}^k\frac{x^i}{i!}\right)^m$$ 注意由于模数不一定是素数，所以不一定有阶乘逆元，但 EGF 的卷积只需要乘上组合数。

考虑容斥，即把 $\sum_{i=0}^k\frac{x^i}{i!}$ 写成 $e^x-\sum_{i=k+1}^\infty \frac{x^i}{i!}$。如果能够预处理所有 $\left(\sum_{i=k}^\infty \frac{x^i}{i!}\right)^m$，就能够在 $O(n^2\log n)$ 时间内计算答案（因为 $mk\le n$）。

这里 $m$ 的范围是 $\frac{n}{k}$，按照 $k$ 从大到小预处理，每次只需给内部的式子加上一项，展开后是 $O(m)$ 项已知的式子求和。因此可以在 $O\left(\sum_{k=1}^n \frac{n^3}{k^2}\right)=O(n^3)$ 时间内预处理所有的值。对于每组数据，还要对 $0\le i\le n$ 计算 $m\choose i$，可以通过快速幂计算 $(1+x)^m\bmod x^{n+1}$ 在 $O(n^2\log m)$ 的时间内计算。因此总复杂度是 $O(N^3+\sum n^2(\log n+\log m))$。

对于整数 $B$，我们只预处理 $k\ge B$ 的值，复杂度是 $O\left(\frac{n^3}{B}\right)$。对于 $k< B$，我们要计算的是一个短多项式的幂，可以通过 ODE（$f'g=mg'f$）来计算，注意 EGF 的求导就是移位，所以不需要除法，复杂度是 $O(nk)$。总时间复杂度 $O\left(\frac{N^3}{B}+\sum n B^2+\sum n^2(\log n+\log m)\right)$。

官方题解里有 $O(\sum n^2\log n)$ 的做法。

N. Python Program

外层循环直接模拟，内层循环用等差数列求和。

时间复杂度 $O(|a-b|)$。

A. Bus Analysis

不妨将价格除以 $2$，变为 $1$ 和 $3$，最后将答案乘 $2$ 即可。

先考虑对于给定的 $t_1,t_2,\ldots,t_n$，如何计算最小代价。

设 $\mathrm{dp}(i,j)$ 表示用 $j$ 的代价覆盖了前 $i$ 个点，最多还能覆盖多长的距离。设覆盖前 $i$ 个点的最小代价为 $x$，则只有 $f(i,x),f(i,x+1),f(i,x+2)$ 的值有用。这是因为在如果前 $i$ 个点花费了至少 $x+3$ 的代价，一定不比“花费 $x$ 的代价覆盖前 $i$ 个点，然后再买一张 $3$ 元的票”优。

于是，在 DP 的过程中我们只需要记录 $x,f(i,x),f(i,x+1),f(i,x+2)$ 这些值。现在变为计数问题，只需要将这些值记在状态里面。并且注意到，我们只需要求代价的和，所以不需要将 $x$ 计入状态，只需在代价变大时统计进答案。

时间复杂度 $O(n\cdot 75^3)$。实际上，状态数的常数非常小，有用的三元组 $(a,b,c)$ 都满足 $0\le a\le a+20\le b\le b+20\le c\le 75$。

B. Missing Boundaries

首先，对于已经确定两个端点的区间，它们一定不能相交。

对于已经确定一个端点的区间，确定的端点一定不能包含在已经确定的区间里面，且互不相同。

剩下的区间可以任意填，我们可以计算出最小和最大的可能区间数量，判断输入的区间数量是否在范围内即可。

最大的区间数量就是（$L-$ 两端点确定的区间的长度和 $-$ 一个端点确定的区间个数）。

最小的区间数量就是相邻且差大于 $1$ 的右端点和左端点的对数（包括开头和结尾）。

时间复杂度 $O(N\log N)$。

C. Price Combo

考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 $a_i>a_j$ 且 $b_i< b_j$，那么在商店 A 购买物品 $i$ 、商店 B 购买物品 $j$ 一定是不优的（交换之后一定不劣）。因此，假设我们把一个物品看做点 $(a_i,b_i)$，那么一定存在一条右上到左下的折线，折线上以及左上方的物品在商店 A 购买，折线右下方的物品在商店 B 购买。我们对这条折线进行 DP。

不妨设 $a_i,b_i$ 互不相同。我们考虑从右上到左下确定折线，当折线向左的时候，加入折线上方的 $a_i$ 产生的贡献；折线向下的时候，加入折线右方的 $b_i$ 产生的贡献。注意因为是买一送一，因此只有第 $1,3,5,\ldots$ 个会产生贡献。

显然我们只需要将 $(a_i,b_i)$ 作为折线的关键点。为了方便起见，我们可以加入 $(+\infty,+\infty),(-\infty,-\infty)$。

设 $\mathrm{dp}(i,p,q)$ 是折线走到了 $(a_i,b_i)$，选择的 $a$ 个数奇偶性是 $p$，$b$ 个数奇偶性是 $q$ 的最小代价。那么假设 $(a_i,b_i)$ 从 $(a_j,b_j)$ 转移来（$a_i< a_j,b_i< b_j$），则需要加上的贡献是 $a_i< a_k< a_j$（$b_k>b_j$）和 $b_i< b_k< b_j$（$a_k>a_i$），以及 $a_i$ 的贡献。

考虑按照 $a_i$ 从大到小扫描线，用线段树维护转移。线段树以 $b$ 作为下标，维护 DP 值加上 $a_k$ 的贡献的最小值。对于 $a_k$ 的贡献，只需在扫描线时在线段树上做前缀加（$b_j< b_k$）。注意这里的加法标记实际上是（$0$ 位置加上的值，$1$ 位置加上的值，加的数的个数）三元组。对于 $b_k$ 的贡献，考虑直接在线段树上维护，即每个结点维护 $\mathrm{dp}(j)$ 加上小于 $b_j$ 的 $b$ 的贡献后的最小值，以及 $b$ 的贡献。这里 $b$ 的贡献本质上和 $a_k$ 的加法标记一样。合并时，DP 值应当是左区间的 DP 值以及（右区间的 DP 值加上左区间 $b$ 的贡献）的较小值。这样，要求 $\mathrm{dp}(i)$，只需要在线段树上查询后缀 $(b_i,+\infty)$。

时间复杂度 $O(N\log N)$。

D. Data Determination

不妨设 $a_1\le a_2\le \cdots\le a_n$。

当 $k$ 是奇数时，需要存在 $i$，满足 $a_i=m,i-1\ge\frac{k-1}{2},n-i\ge\frac{k-1}{2}$。

当 $k$ 是偶数时，需要存在 $i< j$，满足 $a_i+a_j=2m,i-1\ge \frac{k}{2} -1,n-j\ge\frac{k}{2}-1$。注意对于相同的 $(a_i,a_j)$，$i$ 和 $j$ 离得越近越好，这样的 $(i,j)$ 只有 $O(n)$ 对。

时间复杂度 $O(n\log n)$。

E. Express Eviction

解法 1

最小割。注意到存在路径当且仅当不存在左下区域到右上区域、每个格子都有居民、且相邻格子行列差都不超过 $2$ 的路径。我们认为左下边界和左下区域是相邻的，右上边界和右上区域是相邻的。

因此我们可以对每个有居民的格子建两个点 $(a_u,b_u)$，如果它是左下边界则连边 $(S,a_u,+\infty)$，右上边界则连边 $(b_u,T,+\infty)$，同时连边 $(a_u,b_u,1)$ 代表可以花费 $1$ 的代价删除这个格子。对于行列差都不超过 $2$ 的每对格子 $u,v$，连边 $(b_u,a_v,+\infty)$。这个图的最小割即为答案。

时间复杂度 $O(\mathrm{Maxflow}(HW,HW))$。

解法 2

最短路。考虑普通的最短路在什么时候会得不到最优解。

.#....
....#.
...#..
###...
###..#
###...

如这个例子，只需删除第三行的第四个格子。我们注意到这样的路径实际上是经过了一个格子相对的两个角，但我们的状态中并没有记录经过的格子，所以导致重复计算代价。

考虑所有经过两次的格子，如果一个有居民的格子 $u$ 的两次经过在另一个格子 $v$ 的两次经过之间，我们不如额外花费 $1$ 的代价直接穿过格子 $v$。因此可以假设没有这样的两个格子 $(u,v)$。在这个前提下，我们可以发现路径上的每一个点至多在两个格子的两次经过之间（路径的两侧各一个），通过在状态中记录这两个格子，我们可以做到 $O(H^3W^3)$ 的时间复杂度。

进一步地，假设我们依次经过了格子 $u,v$，那么下一步一定是从 $v$ 走到格子 $u$ 的对角。并且如果在下一次经过 $u$ 之前我们花费了额外的代价，也是不如直接穿过 $u$ 的。因此我们只需要记录一个之前经过的格子，并加一种额外的转移，即当前位置是 $x$，经过了 $v$，对于 $v$ 的每个对角相邻的点 $w$，如果 $x$ 可以不花费额外代价到达 $w$，则可以直接转移到位置 $w$，经过了 $x$。转移可以通过从每个点 BFS 预处理。

时间复杂度 $O(H^2W^2)$。

F. Fibonacci Fusion

不妨设 $a_1\le a_2\le \cdots\le a_n$。

枚举 $j$，则 $a_j< a_i+a_j\le 2a_j$，满足这样条件的斐波那契数只有至多两个，假设我们能求出这两个斐波那契数，就只需要求某个数的出现次数。

由于 $a_i$ 非常大，对应的斐波那契数也非常大，所以我们计算斐波那契数对大素数取模的值（避免碰撞），同时需要估算对应的数的下标。

因为 $F_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)\approx \frac{1}{\sqrt 5}\left(\frac{1+\sqrt5}{2}\right)^n$ ，所以可以用 $n\approx \log_{\frac{1+\sqrt 5}{2}}{\sqrt 5a_i}$ 来估算。

时间复杂度 $O(n\log n+\sum\log a_i)$。

G. Game of Geniuses

答案等于 $\max_i\min_j a_{ij}$。

设答案为 $x$，答案大于等于 $x$ 是平凡的，先手可以删除除最小值等于 $x$ 的行以外的其余行。

要证明答案小于等于 $x$，我们只需要证明每轮后，后手都能保证每行都有小于等于 $x$ 的数。不妨设先手删除了第一行，则后手找到剩余 $n-1$ 行中各一个小于等于 $x$ 的数，标记其所在列，然后删除未被标记的列即可。

时间复杂度 $O(n^2)$。

H. Henry the Plumber

因为每个水管都必须立即转弯，所以答案至少是 $2$。

而答案不超过 $4$，因为可以分别连平行于 $z$ 轴的水管，到同一个 $z$ 之后垂直于 $z$ 轴连接起来（如果两点连线平行于 $z$ 轴则直接连）。

分类讨论：

• 如果 $(x_1,y_1,z_1)-(x_2,y_2,z_2)$ 垂直于 $(p_1,q_1,0)$ 和 $(p_2,q_2,0)$，则答案为 $2$。
• 否则答案至少为 $3$。答案为 $3$ 当且仅当存在一个中间点 $P$，和 $(x_i,y_i,z_i)$ 的连线垂直于 $(p_i,q_i,0)$。即 $P$ 在经过 $(x_i,y_i,z_i)$ 且垂直于 $(p_i,q_i,0)$ 的平面上。
• 如果这两个平面平行，则答案为 $4$。
• 否则找到这两个平面的交，设为 $(x_0,y_0,z)$（一条平行于 $z$ 轴的直线）。现在要确定 $z$ 的值，使得 $P$ 的夹角为直角，即 $(x_0-x_1,y_0-y_1,z-z_1)$ 和 $(x_0-x_2,y_0-y_2,z-z_2)$ 的点积为 $0$。
• 如果 $(x_0,y_0)$ 和某个 $(x_i,y_i)$ 重合，则满足条件的 $P$ 就是 $(x_i,y_i,z_{j})$，如果 $z_1\ne z_2$ 则答案为 $3$，否则答案为 $4$（因为水管长度不能为 $0$）。
• 否则，条件是一个关于 $z$ 的二次方程，只需判断判别式是否大于等于 $0$。大于等于 $0$ 则答案为 $3$，否则答案为 $4$。

时间复杂度 $O(1)$。

I. ICPC Inference

枚举获得金银铜牌的队伍。铜牌一定是通过了一个题目，且罚时尽量大。金牌一定是通过了尽量多的题目，且罚时尽可能小。

我们可以将分数设为 $M\cdot \mathrm{num}-\mathrm{penalty}$，其中 $M$ 是一个非常大的数。则分数越大的人排名越高。

考虑银牌可能的分数，因为铜牌只通过一个题，银牌分数应当在不小于铜牌的前提下尽可能小，因此有用的分数只有通过一个题的情况以及通过两个题且罚时最大。设这些可能的分数是 $s_1< s_2< \ldots< s_k$，则满足 $s_i<\mathrm{bronze}\le\mathrm{gold}< s_{i+1}$ 的金铜牌是不合法的（当然还有小于 $s_1$ 和大于 $s_k$ 的情况）。

我们可以在 $O(\log N)$ 的时间里面对每一个区间计算答案，但是区间的数量可以是 $O(N^2)$ 的。注意到罚时 $K=20$ 比较小，而可能的罚时都形如 $t_i+K\cdot c$（$0\le c< i$），因此可能的罚时可以写成 $O(N)$ 个段，每个段以 $K$ 为周期。对于跨段的区间我们可以 $O(\log N)$ 计算。而对于段内我们可以抽象成 $O(K)$ 个以下询问：

• 有多少对 $(\mathrm{bronze},\mathrm{gold})$ 满足 $\mathrm{bronze}\bmod K=i$，$l\le \mathrm{bronze}\le r$ 且 $\mathrm{gold}-\mathrm{bronze}\le j$。

这样的 $(\mathrm{bronze},\mathrm{gold})$ 也只有 $O(NK)$ 对，预处理之后可以 $O(\log N)$ 回答询问。

注意金银铜牌必须互不相同，因此需要做一些容斥。

时间复杂度 $O(NK\log N)$。

J. Juliet Unifies Ones

数据范围很小，所以做法很多。

一个线性的做法是分成三段，分别是 $0,1,0$，设 $\mathrm{dp}(i,j)$ 表示考虑 $i$ 个字符，目前在第 $j$ 段，至少要删几个字符。

K. Routing K-Codes

如果 $K(b)=\left\lfloor\frac{K(a)}{2}\right\rfloor$ 则我们将边定向为 $a\to b$。因为所有 $K(x)$ 互不相同，因此每个点的出度都不超过 $1$，入度不超过 $2$，且图中不存在环，因此只可能是内向二叉树。因此如果 $m\ne n-1$ 则无解。

假设确定了根，则根的值为 $0$ 或 $1$（度数小于 $2$ 则为 $0$，等于 $2$ 则为 $1$），深度不超过 $32$ 或 $31$，每个孩子的值是 $2K(x)$ 或 $2K(x)+1$。最小的代价和可以通过 DP 求出。使用换根 DP 即可求出每个点作为根的答案。

时间复杂度 $O(n+m)$。

L. Random Numbers

注意到长度为 $k$ 的区间的和的期望是 $k\cdot \frac{n+1}{2}$，因此当 $k$ 距离 $\frac{n}{2}$ 较近时才有较大的概率存在合法区间。当 $k$ 较小的时候，因为总的组合数量不多，因此也有一定的概率存在合法区间。

因此只需设置常数 $B$，枚举所有长度在 $[1,B]$ 或 $\left[\frac{n}{2}-B,\frac{n}{2}+B\right]$ 中的区间检查即可。

时间复杂度 $O(nB)$。例如 $B$ 取 $500$ 可以通过此题。

M. Mathematics Championships

答案等于前 $2^i$（$0\le i\le k$）大数和的最大值。排序后即可计算。

时间复杂度 $O(n2^n)$。

A. Coprime Array

注意到我们只关心 $s\bmod x$ 的值（答案绝对值要求在 $10^9$ 以内，但是任何一组解都可以通过调整符合这个范围，所以可以忽略这个限制），将 $x$ 分解后，只需要求出每个 $p^k$ 的解，就能通过 CRT 合并出 $x$ 的解。

显然答案等于 $1$ 当且仅当 $\gcd(s,x)=1$。

剩下的情况，除了 $s$ 是奇数且 $x$ 是偶数的情况，都能构造出长度为 $2$ 的解。

$s$ 是奇数且 $x$ 是偶数的情况可以先分出一个 $1$，因此可以构造出长度为 $3$ 的解。

实现时其实可以利用随机避免分解和 CRT，随机到一个解的概率至少是 $\prod_{p|x}\frac{\max\{1,p-2\}}{p}$。

B. Square Locator

因为点 $A$ 在 $y$ 轴上，所以点 $A$ 的坐标可以直接算出。枚举 $ABCD$ 是逆时针还是顺时针，设点 $B$ 的坐标是 $(x,y)$，则可以通过点 $B$ 和点 $C$ 到原点的距离列出两个方程，从而直接解出 $x,y$ 并判断。

C. -is-this-bitset-

对于深度 $d\le 11$ 的点 $i$，将 $a_i$ 设为 $2^{20-d}$。因为树是二叉树，所以至多改变 $2^{12}-1=4\,095$ 个点的 $a_i$。

改变之后，每条链上的前 $12$ 个点就可以凑出 $[0,2^{21})$ 中所有 $2^9=512$ 的倍数。因此对于 $d>11$ 的点，只需要考虑模 $512$ 的每种余数能凑出的最小的数，可以在 $O(512)$ 的时间 DP 求出。

为了进一步减小空间消耗，注意到每条链上 DP 的改变量不会超过 $\max\{b_i\} < 2^{21}$，因此只需记录 DP 数组发生的改变，回溯时撤销即可。

设 $V=\max\{b_i\},k=5\,000$，则时间复杂度为 $O(nV/k)$，空间复杂度为 $O(n+V)$。

D. Cycle Game

我们认为最外圈边界都是白格子，则存在一个内部非空的环当且仅当存在一个格子，将这个格子视为白格子后白格子的八连通块至少有两个（即存在一个白格子和边界不连通）。

加入一个黑格子后，如果存在这样的格子，那么其中的一个一定与新加入的格子相邻。因此只需使用线段树分治和可撤销并查集维护连通性，在每个时刻枚举周围的所有格子并判断这次操作是否应该进行。

时间复杂度 $O(nm\log ^2 (nm))$。

E. Sum of Squares

F. Alternating Cycle

G. Touching Grass

如果询问的是直线，则问题可以转化为直线和点集的上凸包是否相交，只需在凸包上二分。

线段询问可以通过线段树转化为直线询问，即按 $x$ 排序建线段树，对线段树上的每个区间都求凸包。

这样的空间复杂度是 $O(n\log n+m)$，采用类似分治的方式离线回答询问可以优化为 $O(n+m)$。

将线段按斜率排序后可以避免二分，改用双指针，总时间复杂度 $O((n+m)\log n)$。

H. Game Design

将 $i$ 到 $p_i$ 连边，可以看作每个点入度和出度都是 $1$ 的有向图。设 $f(i,j)$ 为考虑前 $i$ 个点，有 $j$ 条入边和出边的另一端还未确定（大于 $i$）。

考虑 $i$ 的连边，有如下四种转移。

• 入边和出边都向后，转移到 $j+1$，方案数 $1$。
• 入边向后，出边向前，转移到 $j$，方案数 $j$。
• 入边向前，出边向后，要求 $s_i=1$，转移到 $j$，方案数 $j$。
• 入边和出边都向前，要求 $s_i=1$，转移到 $j-1$，方案数 $j^2$。

时间复杂度 $O(n^2)$。

I. Geometry Hacking

J. Non-Interactive Nim

A. Counting Permutations

对于所有满足条件的排列，二元组序列 $(a_{p_i}\bmod m_1,a_{p_i}\bmod m_2)$ 一定是相同的，也就是按 $a_i\bmod m_1$ 为第一关键字，$a_i\bmod m_2$ 为第二关键字升序排序。

如果这个序列不合法则无解，否则方案数为每个 $(a_i\bmod m_1,a_i\bmod m_2)$ 二元组出现次数的阶乘乘积。

时间复杂度 $O(n\log n)$。

B. Bookshelf Tracking

如果只有 E 操作，则维护每本书的位置，就可以 $O(1)$ 进行交换。

如果有 R 操作，注意到 R 操作的本质是将位于前一半的书按编号降序排序，后一半的书按编号升序排序。因此，在最后一次 R 操作之前，只需维护每本书是在前一半还是后一半。排序后再处理最后的一段 E 操作即可。

时间复杂度 $O(n+q)$。

C. Painting Fences

最优解一定是从一个极大全黑矩形开始扩展。这样的矩形共有 $O(nm)$ 个，可以通过枚举底端然后笛卡尔树求出。

考虑求从一个矩形扩展到全部的步数。显然两维是独立的，因此只需要考虑 $[l,r]$ 扩展到 $[0,n]$ 的最少步数。

如果 $l=0$ 或者 $r=n$，显然最优解是长度每次翻倍。

对于一般情况，枚举 $l=0$ 和 $r=n$ 哪个先满足。不妨设 $l=0$ 先满足。设初始时 $d=\left\lceil \frac{l}{r-l}\right\rceil$，则至少需要 $\left\lceil\log_2{(d+1)}\right\rceil$ 步。但是一直向左对称可能会导致一些浪费。事实上，最优解是：第 $i$ 轮，如果 $d$ 的二进制从低到高第 $i$ 位是 $1$，则向左对称，否则向右对称。

因此从一个矩形开始扩展的最小步数可以在 $O(\log nm)$ 甚至 $O(1)$ 的时间内求出。

总时间复杂度 $O(nm\log nm)$ 或 $O(nm)$。

D. Function with Many Maximums

首先要注意到，假设 $a_i$ 是降序排序，则 $f(a_i)=\sum_{j=1}^ia_j+ia_i$。如果不考虑 $a_i$ 必须是整数的条件，令 $a_i=\frac{1}{i(i+1)}$ 可以使所有 $f(a_i)$ 相同。

考虑找一个大数 $M$（大约为 $Cn^4$ 级别），然后令 $a_i=\left\lfloor \frac{M}{i(i+1)}\right\rfloor$，然后对其进行调整。我们希望使得 $f(a_{n}),f(a_{n-2}),f(a_{n-4}),\ldots,f(a_{n-2(b-1)})$ 是最大值，因此对于 $i< n-2(b-1)$，只需令 $a_i=a_{i+1}+1$。注意这时 $a_1$ 也就是 $a_i$ 的最大值不超过 $O(Cn^2)$，符合题目要求。

对于后面部分的调整，首先需要将 $f(a_i)$ 调整成递增，这只需将函数值下降位置的 $a_i$ 增加 $O(n)$ 的值。这是因为原来相邻函数值的差是 $O(n)$ 的，所以调整后累计的差是 $O(n^2)$，而将 $a_i$ 增加 $1$ 会使得 $f(a_i)$ 增加 $i+1$。

调整后，相邻函数值的差仍然是 $O(n)$ 的，而相邻 $a_i$ 的差是 $\Theta(Cn)$，因此将 $a_{2i+1}$ 的值减少 $f(a_{2i+2})-f(a_{2i})$ 就能使得 $f(a_{2i+2})=f(a_{2i})$。

E. Building a Fence

分类讨论。不妨设 $w\le h$。

• 如果 $s\le w\le h$，那么从一个角开始贪心铺放，不可能出现一个 $s$ 被分成三段的情况，因此答案可以取到下界 $\left\lceil \frac{2(w+h)}{s}\right\rceil$。
• 如果 $w\le h< s$，那么答案可能是 $2,3$ 或 $4$。
  • 要答案为 $2$，只可能是两个 $s$ 都被分成了两段，即 $w+h=s$。
  • 要答案为 $3$，肯定有 $k$ 个 $s$ 恰好拼了 $k+1$ 条边。
    • $k=1$，即 $2w=s$ 或 $2h=s$。
    • $k=2$，即 $2w+h=2s$ 或 $2h+w=s$。
    • $k=3$，即 $2(w+h)=3s$。
  • 否则答案为 $4$。
• 如果 $w< s\le h$。
  • 如果 $2w+h\ge 2s$，那么可以先拿两个 $s$ 分出两个 $w$，剩下部分拼到同一个长边，然后从这条边开始贪心，能取到下界 $\left\lceil \frac{2(w+h)}{s}\right\rceil$。
  • 否则答案为 $3$ 或 $4$，分析同上，但因为大小关系的限制只可能 $k=3$，即 $2(w+h)=3s$。

F. Teleports

注意到经过任意的操作后，我们都知道可能的宝藏位置是一个区间。设 $f(l,r)$ 是已知宝藏在第 $l$ 个到第 $r$ 个箱子时，找到宝藏的最小代价。

转移如下。

• 枚举选择的传送器 $x$，则新的可能的宝藏范围是 $[2x-r,2x-l]$。
  • 如果 $1\le 2x-r\le 2x-l\le n$，则 $f(l,r)\le f(2x-r,2x-l)$。
  • 如果 $2x-r< 1$，则 $[2x,r]$ 中的宝藏无法传送，$f(l,r)\le \max\{f(1,2x-l),f(2x,r)\}$。
  • 如果 $2x-l>n$，则 $[l,2x-n-1]$ 中的宝藏无法传送，$f(l,r)\le \max\{f(2x-r,n),f(l,2x-n-1)\}$。

注意到转移图是一个关于区间长度 $r-l$ 的分层图，每一层中只有第一类转移。因此可以从小到大枚举 $r-l$，执行所有的第二、三类转移，然后使用 Dijkstra 进行第一类转移。这里是稠密图所以可以使用 $O(n^2)$ 的 Dijkstra（当然堆优化的 Dijkstra 也很快）。

时间复杂度 $O(n^3)$。

G. Exponent Calculator

因为只有加法、减法和乘法，因此不考虑牛顿迭代。考虑用 $e^x=\sum_{n=0}^\infty \frac{x^n}{n!}$ 来逼近。但是这样在 $|x|$ 较大时收敛较慢。因此考虑先将 $x$ 除以 $2^B$，然后展开到 $x^T$ 项，最后将结果平方 $B$ 次。实验可以发现 $T=7,B=10$ 时较优，可以在 $x=20$ 时达到 $10^{-12}$ 以下的相对精度。

H. Ancient Country

考虑所有城市的顶点，不可能出现 $i < j < k < l$ 满足 $P_i$ 和 $P_k$ 在同一个城市，并且 $P_j$ 和 $P_l$ 在同一个城市（否则 $P_iP_k$ 和 $P_jP_l$ 就会相交或是在国家范围之外）。因此这些城市的顶点形成一个树形结构。即设包含最小顶点的城市的顶点为 $P_{i_1},P_{i_2},\ldots,P_{i_k}$，那么剩余的城市顶点一定分布在 $[i_1+1,i_2-1],[i_2+1,i_3-1],\ldots,[i_k+1,n]$ 这些区间中。

因此我们可以设计区间 DP，即 $f(l,r)$ 表示只是用下标在 $l$ 到 $r$ 的顶点，所构造城市的最大保护级别。转移如下。

• 假设 $P_l$ 不属于某个城市，则 $f(l,r)\gets f(l+1,r)$。

• 否则我们要选一个包含 $P_l$ 的凸包，然后用凸包的权值加上凸包顶点间的区间的 $f$ 值之和来更新 $f(l,r)$。这一步也可以用 DP 进行。

  • 首先枚举 $i$ 连的第一条边 $P_iP_s$，然后令 $g(j,k)$ 表示凸包最后一条边是 $P_jP_k$ 的最大权值。转移是枚举下一条边 $P_kP_e$，然后转移到 $g(k,e)$。最后检查一下连回 $l$ 是否合法并更新答案。需要枚举第一条边是因为要检查 $P_kP_iP_s$ 这个角是否合法。注意这里判断凸包只需要相邻三个点的夹角，因为下标递增，必然是不会自交的。

具体实现时，可以从大到小枚举 $l$，然后进行 DP。枚举 $l,s$ 后，DP 的复杂度是 $O(n^3)$。注意到转移可以用极角序优化，即枚举 $k,e$，可以转移到 $g(k,e)$ 的 $i$ 是极角序上的一段。事实上，我们不需要记录极角序，因为下标递增，每个点所连出的边按下标排序就是极角序，因此枚举 $k,e$ 后，可以转移的 $i$ 是一个前缀，用双指针维护即可。

总时间复杂度 $O(n^4)$。

I. Marks Sum

如果长度小于 $2\,000$，可以直接返回 $d=info=0$。

如果长度大于等于 $2\,000$，我们一定能找到一个前缀，使得剩余字符数小于 $2\,000$，且总和是 $2\,000$ 的倍数或其加 $1$。我们令 $info=2x+y$（$0\le y\le 1$）表示前缀的总和等于 $2\,000x+y$。因为字符串长度不超过 $10^6$，因此 $x< 1\,000$，是足够的。

第二次时只需根据 $info$ 计算出前缀的总和，在加上输入串的总和即可。

J. Prefix Divisible by Suffix

枚举选择最短的后缀。如果后缀有前导 $0$，则去掉之后仍然满足条件。因此满足条件的最短后缀长度不超过 $7$（如果大于 $7$ 则前缀小于后缀）。

因为我们钦定枚举的后缀是最短的一个，需要枚举更短的一些进行容斥。若干后缀都满足的数形如 $km+a$，可以用扩展欧几里得算法求出。

时间复杂度 $O(10^7\cdot 2^7\cdot \log n)$。但是注意到在后缀较长时，对于很多的集合，满足条件的数的大小都超过了 $n$。我们在枚举的时候对这种情况直接剪枝，总枚举次数实际上远小于这个上界。

K. Train Depot

首先可以把所有列车转化为 $s_i$ 到 $t_i$ 的路径（$t_i$ 是 $s_i$ 的祖先），价值为 $c_i$，然后选择若干条点不相交的路径使得总价值最大。

设 $f(x)$ 为在 $x$ 的子树里面选择路径的最大价值。如果 $x$ 不是某条路径的顶端则 $f(x)\gets \sum_{y\in ch(x)}f(y)$。

如果选择了 $x\to y$ 的路径，那么 $y$ 到 $x$（不包括 $x$）的路径上的每一个点的兄弟以及 $y$ 的所有孩子 $z$ 会贡献 $f(z)$。反过来考虑，每个点 $x$ 会对底端是 $x$ 的父亲或 $x$ 的兄弟子树中的点的路径有贡献，在 DFS 序上即 $[in_{parent_x},in_x)$ 和 $[out_x,out_{parent_x})$ 这两个区间。使用线段树或树状数组维护这个贡献即可。

时间复杂度 $O((n+\sum k_i)\log n)$。

L. Array Spread

二分答案 $x$，如果有一种序列满足每个区间的总和在 $[1,x]$ 中，说明答案不大于 $x$。

设 $s_i$ 是前 $i$ 个数的和，则限制为 $s_i\ge s_{i-1}$ 和 $1\le s_{r_i}-s_{l_i-1}\le x$，显然是差分约束的形式。离散化之后点数和边数都是 $O(m)$，因此判断负环的时间复杂度是 $O(m^2)$。这里也可以看出答案是分子和分母不超过 $O(m)$（分母不超过简单环长度也就是图中点数，分子不超过图中除 $x$ 外的边权和）的分数。因此二分次数是 $O(\log m)$，二分之后可以根据实数值还原答案。也可以直接对这 $O(m^2)$ 个分数二分。

总时间复杂度 $O(m^2\log m)$。

事实上，我们可以去掉二分。将边权为 $x$ 的边称为特殊边，剩下的是普通边。令 $f(i,v)$ 表示从任意点开始，经过恰好 $i$ 条特殊边，到达 $v$ 的路径的普通边边权和的最小值。则答案等于 $$\max_v\min_{i=0}^{n-1}\frac{f(i,v)-f(n,v)}{n-i}$$

其中 $n$ 是顶点数。

证明见此论文。

M. Uniting Amoebas

每次将最大值和相邻的合并就可以做到 $\sum_{i=1}^n a_i-\max_{i=1}^n\{a_i\}$。

显然这是最优解，因为每次花费 $v$ 的代价至多使得最大值增加 $v$。

A. Interesting Paths

只保留能够被 $1$ 到 $n$ 的路径包含的点和边，则答案为边数 $-$ 点数 $+2$。

注意到每次新加入的边一定是若干条路径，且如果大于一条或路径经过了某个已经经过的点，则可以分多轮依次加入。因此最优解中，每次新加入的边都是一条路径，且除首尾外，经过的点都没有出现过。这样的路径满足边数 $-$ 点数 $=1$，算上最初的 $1$ 和 $n$，答案就是边数 $-$ 点数 $+2$。

时间复杂度 $O(n+m)$。

B. Roars III

考虑固定根的情况，有一个显然的贪心算法：自底向上，每个顶点合并子树的人所在顶点集合，如果该顶点没有人，则将子树内最深的人移至该顶点（实际上是链上的点都往上移一步，但是等价）。

需要支持集合的合并、求最大值、删除最大值。可以使用左偏树维护，可持久化以后自然可以实现换根。换根时不能直接使用顶点的深度了，而是需要在每个点处 $+1$，因此需要维护加法标记。

时间复杂度 $O(n\log n)$。

C. Radars

注意到，所有格子都被覆盖等价于四个角落都被覆盖。枚举四个角分成若干集合的所有方案，然后对每个集合找到一个雷达全部覆盖的最小代价，然后求和，即是该方案的代价。找到所有方案的最小值即是答案。

时间复杂度 $O(n^2)$。

D. Xor Partitions

设 $f(i)$ 表示长度为 $i$ 的前缀的所有划分方案的权值和。则 $$f(i)=\sum_{j=0}^{i-1}f(j)\cdot (a_{j+1}\oplus \cdots \oplus a_i)$$ 令 $S(i)$ 是 $a_i$ 的前缀异或和，将异或和拆位，令 $g(k,c)$ 表示 $S_i$ 的第 $k$ 位为 $c$ 的 $f(i)$ 之和，即可在 $O(\log A)$ 的时间内转移。

时间复杂度 $O(n\log A)$。

E. Pattern Search II

可以注意到，我们可以找到一个 $S_n$ 使得 $|S_n|=O(|t|)$，使得答案可以在 $S_n$ 中被找到。

这是因为，设 $n$ 是最小的非负整数满足答案能在 $S_n$ 中被找到。如果 $n\ge 2$，$S_n=S_{n-1}S_{n-2}$，因为答案不在 $S_{n-1}$ 或 $S_{n-2}$ 中，所以答案一定是 $S_{n-1}$ 的一个后缀加上 $S_{n-2}$ 的一个前缀。因为 $S_n$ 中没有相邻三个相同的字符，所以答案的长度一定是 $O(|t|)$，而 $S_n=S_{n-1}S_{n-2}=S_{n-2}S_{n-3}S_{n-3}S_{n-4}=S_{n-2}\underline{S_{n-3}S_{n-4}}S_{n-5}S_{n-4}$。如果 $S_{n-4}\ge 3|t|$，则答案可以在 $S_{n-2}$ 中找到，矛盾。因此 $S_{n-4}< 3|t|$，从而 $S_n=O(|t|)$。

枚举 $S_n$，满足答案是 $S_{n-1}$ 的一个后缀加上 $S_{n-2}$ 的一个前缀，枚举 $|t|$ 中的分割点，则需要计算 $S_{n-2}$ 最短的包含子序列 $t[i:]$ 的前缀，后缀同理。这可以用 DP 在 $O(|t|\log |t|)$ 时间内计算。（上述证明只是为了说明 $n=O(\log |t|)$）。

总时间复杂度 $O(|t|\log |t|)$。

F. Waterfall Matrix

这个问题实际上就是网格图 DAG 上的 $L_1$ 保序回归问题。使用分治，则需要解决总规模 $O(n\log n)$ 的如下问题：

• 给定若干个格子，每个格子权值是 $\pm 1$，找一条左下到右上的折线，使得折线左上方的格子权值和最大。

这个问题可以通过扫描线 + 线段树维护 DP 在 $O(n\log n)$ 时间内解决。

总时间复杂度 $O(n\log ^2n)$。

G. Puzzle II

注意在经过 $(c,d),(c,d+1)$ 的操作后，假设 $S$ 从 $c$ 开始的 $k$ 个字符是 $aX$，$T$ 从 $d$ 开始的 $k+1$ 个字符是 $bYc$，则操作后 $S$ 变为 $Xc$，$T$ 变为 $abY$。整体上讲，我们通过两次操作交换了 $S$ 中的 $a$ 和 $T$ 中的 $c$。因此，只需交换两个串中出现较少的字符，即可在不超过 $n$ 次操作后达成目标。

具体的实现中，不妨设 $S$ 中 $\mathtt{B}$ 的出现次数更少，则我们需要找到 $S$ 中的一个 $\mathtt{B}$ 和 $T$ 中的一个 $\mathtt{C}$ 并通过上述操作交换。由于操作还会对其他位置造成影响，不能暴力模拟。我们可以用两个双端队列分别维护 $S$ 中长为 $k$ 和 $T$ 中长为 $k+1$ 的窗口，并只在窗口中进行交换。交换后，移动窗口来找到下一个可以交换的位置。总的移动次数是 $O(n)$ 的。

时间复杂度 $O(n)$。

H. Weather Forecast

二分答案 $x$，令 $b_i=a_i-x$，则要把 $b_i$ 分成 $k$ 段，每段总和大于 $0$。这等价于求 $b_i$ 的前缀和的 LIS（必须包含 $0$ 和 $n$），可以在 $O(n\log n)$ 时间内求解。

总时间复杂度 $O(n\log n\log \epsilon^{-1})$。

I. Mercenaries

因为询问的条件是 $a\cdot S+b\cdot M\ge c$，显然我们只需要保留 $(S,M)$ 的凸包。考虑二分答案，然后改为求一个区间 $a\cdot S+b\cdot M$ 的最大值。我们考虑预处理出对线段树上的每个区间，只考虑区间中的点和边，走到右端点得到的 $(S,M)$ 的凸包。

设从任意点走到右端点的凸包为 $A$，从左端点走到右端点，只考虑边的凸包为 $B$。则有 $$A=(A_l+B_r)\cup A_r\\ B=B_l+B_r\\ $$ 其中 $+$ 表示闵可夫斯基和，$\cup$ 表示取并。

分析一下凸包的点数，如果我们认为 $\sum r_i=O(n)$ $B$ 的点数显然是 $O(n)$，$A$ 的点数则是 $O(n\log n)$。因此总共 $\log n$ 层，凸包的总点数为 $O(n\log ^2n)$。

要计算区间中 $a\cdot S+b\cdot M$ 的最大值，我们只需要对线段树上定位到的每个结点的 $A,B$ 都求出这个最大值即可。

查询时先二分，再在线段树上的每个结点凸包二分求出最大值，复杂度 $O(\log ^3 n)$。使用线段树二分以及对询问 $(a,b)$ 按极角排序分别可以优化掉一个 $\log n$。

总时间复杂度 $O(n\log^2 n+q\log n)$。

J. Polygon II

无法构成多边形当且仅当存在一条边的长度大于等于其余所有边长的总和。

枚举这条边 $i$，其边长为 $x_i$，则要计算的是 $x_i\ge \sum_{j\ne i}x_j$ 的概率，令 $x_i\gets 2^{a_i}-x_i$ 可以发现这个概率等于 $\sum_{i}x_i\le 2^{a_i}$ 的概率。

注意到 $U(0,2^a)=U(0,1)+DU(0,1)+DU(0,2)+\cdots+DU(0,2^{a-1})$，其中 $DU(x,y)$ 表示在 $x,y$ 两个数中均匀随机的随机变量。

从低位到高位 DP，令 $f(i,j)$ 表示考虑最低 $i$ 位，当前进位为 $j$ 的概率。为方便起见，我们计算概率乘上 $\prod_i 2^{a_i}$。无法构成多边形的概率就是所有 $f(a_i,0)$ 的和。转移是 $f(i,j)\cdot {C_i \choose k}\to f(i+1,\lfloor (j+k)/2 \rfloor)$，其中 $C_i$ 是 $DU(0,2^i)$ 的个数。

DP 的初始值 $f(0,j)$ 是 $n$ 个 $U(0,1)$ 的和的整数部分是 $j$ 的概率，可以用容斥计算 $n$ 维体积。

时间复杂度 $O(n^2A)$。

K. Power Divisions

可以发现，好的区间个数并不多。事实上它们的总数是 $O(n\log n)$。

可以用分治求出所有好的区间（同时说明好的区间并不多）：

• 对于跨过中点的区间，假设左右的总和分别为 $L,R$，且 $L\ge R$，则一定有 $R=2^{\lfloor\log L\rfloor+1}-L$，即每个 $L$ 至多对应一个 $R$。$L< R$ 的情况同理。

枚举较大的一边后，可以用哈希找到另一边的位置。这里如果直接对总和哈希，错误率不会超过 $O(A/P)$。如果对二进制位做集合哈希，即每一位随机权值，错误率不会超过 $O(1/P)$。

找到所有区间后，简单 DP 即可求出方案数。

总时间复杂度 $O(n\log n)$。

L. Chords

在随机数据下，答案并不会特别大。事实上答案是 $O(\sqrt n)$ 级别（类似 LIS，但并不会证）。

设 $f(k,i)$ 为最小的 $j$ 满足 $[i,j)$ 可以选出 $k$ 条不相交的弦，若不存在则为 $+\infty$。答案即为最大的 $k$ 满足 $f(k,1)<+\infty$。

转移有两种：

• 不选择连接 $i$ 的弦，则 $f(k,i)=f(k,i+1)$。
• 选择了弦 $(i,j)$（$i< j$），令 $c$ 为在 $(i,j)$ 中最多的不相交弦数（可以通过 $f$ 求出），则 $f(k,i)=f(k-c-1,j+1)$。

时间复杂度 $O(n\sqrt n)$。实现时可以直接假设 $k< 900$，然后按照 $i$ 的顺序转移，比递增 $k$ 的方法缓存更友好，快非常多。

M. Balance of Permutation

考虑逐位确定，则需要计算给定前缀、balance 等于 $b$ 的排列个数。将 $p_i=j$ 看作 $i$ 连向 $j$ 的一条边，则 balance 就是对于所有 $i$，跨过了 $(i,i+1)$ 的边数的和。可以设 $f(i,j,b)$ 表示确定了前 $i$ 个点内部的连边，还有 $j$ 对边（向左和向右各 $j$ 条）跨过了 $(i,i+1)$，目前的 balance 是 $b$ 的排列个数。转移时考虑每个点的入边和出边是向后还是向前匹配一条边。确定了的 $p_i=j$ 就删除对应点的出边和入边，但是这时经过 $(i,i+1)$ 的向左和向右的边数不再相等，而是差为定值。

每次 DP 复杂度 $O(n^4)$，总时间复杂度 $O(n^6)$。

A. Arrested Development

动态规划，$f(i,j)$ 表示考虑前 $i$ 个任务，第一个人总时间为 $j$ 时，第二个人总时间的最小值。

时间复杂度 $O(n^2\max\{a_i,b_i\})$。

B. Champernowne Substring

讨论以下情况：

• 对于位置不超过 $100\,000$ 的情况暴力判断，以下都假设串中出现的都至少是五位数。

• 特判串中出现 $10^k$ 或 $10^k-1$ 的情况，以下都假设串中所有数的长度相等。

• 串中只包含一个数。问号一定贪心填 $0$（首位是 $1$），如果首位是 $0$ 还需要在前面补 $1$。

• 串中包含超过一个数。枚举这个数的开始位置和长度，以及进位的位数（因为串长不超过 $25$ 且都至少是五位数，因此至多有一次进位）。那么进位的部分全部填 $0$ 或 $9$，前一位枚举 $0$ 至 $9$，再之前的位每个数都一样，问号同样贪心填 $0$ 或 $1$。对于每种可能性都检查一遍。

C. Comparator

首先注意到，表达式只有两个输入，我们可以直接枚举这两个输入后求表达式的值。从而，每条语句的效果都可以拆分为不超过 $4$ 条：如果 $x$ 的第 $a$ 位为 $u$ 且 $y$ 的第 $b$ 位为 $v$，则返回 $r$。当两条语句的 $(a,u,b,v)$ 四元组相同时，靠后的语句实际上没有任何效果，因为它所能作用的输入已经全部返回了。因此，我们实际上只需要考虑不超过 $4k^2$ 条语句，每条语句的效果可以在 $O(2^{2k})$ 的时间内暴力处理。

当我们得到了所有 $f(x,y)$ 的值后，就可以统计答案。前两个答案都可以暴力统计，最后的答案枚举 $x,y$ 后使用 bitset 优化即可。

时间复杂度 $O\left(\sum|expr|+k^22^{2k}+2^{3k}/w\right)$。

D. Dihedral Group

二面体群的操作对应到字符串其实就是翻转和循环移位，只需要判断未翻转/翻转的 $d+d$ 是否包含 $t$ 作为子串。

时间复杂度 $O(n)$。

E. House Deconstruction

1. $n=m$ 的情况

首先考虑 $n=m$ 的情况，即人的数量和房子的数量一样多时，如何求最小代价。对于一个方案，设 $c_i$ 表示经过了 $i$ 到 $i+1$ 这条边的人数（这里模 $x$ 相等的下标表示同一个位置，例如 $x+1$ 代表 $1$）。如果是从 $i+1$ 到 $i$ 则 $c_i$ 是经过人数的相反数，显然最优解中不会有一条边两个方向都有人经过。则方案对应的代价是 $\sum_{i=1}^x|c_i|$，需要满足的限制如下：

• 如果 $i$ 位置是人，则 $c_i=c_{i-1}+1$。
• 如果 $i$ 位置是房子，则 $c_i=c_{i-1}-1$。
• 如果 $i$ 位置是空，则 $c_i=c_{i-1}$。

容易发现，$c_i$ 序列几乎是确定的，除了可以整体加上一个任意整数。设一个合法的序列是 $c_i'$，则最小代价为对于任意 $k$，$\sum_{i=1}^x|c_i+k|$ 的最小值。这个函数关于 $k$ 是下凸的，因此可以用三分求出答案。（事实上，$k$ 一定是 $c_i$ 的中位数的相反数。）

2. $n< m$ 的情况：最优解

延续 $n=m$ 的思路，我们可以稍微修改 $c_i$ 的定义，即如果 $i$ 位置是房子，$c_i$ 可以等于 $c_{i-1}-1$ 或 $c_{i-1}$（表示该房子未被选择）。我们可以猜测以下的引理：

引理 1 设 $g(k)$ 为 $c_x=k$ 时的最优解，则 $g(k)$ 是下凸函数。

有了引理 1 之后，对于 $n< m$ 的情况我们同样可以三分 $k$，之后只需解决固定 $c_x$ 之后的问题，即可求出最优解。

引理 1 的证明 只需证明 $2g(k)\le g(k-1)+g(k+1)$。设 $k-1$ 和 $k+1$ 对应的序列分别为 $c_i^{(k-1)}$ 和 $c_{i}^{(k+1)}$。则令 $c_i^{(k)}=\frac{c_i^{(k-1)}+c_i^{(k+1)}}{2}$。该序列几乎满足我们的需求，包括 $c_x^{(k)}=k$ 以及相邻 $c_i$ 之间的关系，并且因为三角形不等式 $|a+b|\le |a|+|b|$，该序列的代价不超过 $\frac{g(k-1)+g(k+1)}{2}$。唯一有问题的地方是当某一处房子只在 $k-1$ 和 $k+1$ 中的一个方案中被选择时，我们会算出 $c_i=c_{i-1}-1/2$。然而，对于每一个极长的小数部分为 $1/2$ 的连续段，整体加上或减去 $1/2$ 就是合法的序列，且其中的一种不会使得代价变大（只需比较正数和负数的数量）。从而我们证明了 $2g(k)\le g(k-1)+g(k+1)$。$\blacksquare$

对于证明中存在小数部分的调整，事实上，即使我们把 $i$ 位置是房子时的限制改为 $c_i\in[c_{i-1}-1,c_i]$，最优解仍然会在所有数都是整数时取到。（提示：仍然可以考虑调整，也可以直接把原问题写成费用流，这样也能得到原问题的凸性。）

接下来只需要考虑固定 $k$ 时如何求最优解。我们可以使用 DP。

设 $f(i,j)$ 表示考虑了前 $i$ 个位置，$c_i=j$ 的最小代价。初始值为 $f(0,k)=0$。转移如下：

• 如果 $i$ 位置是人，则 $f(i,j)= f(i-1,j-1)+|j|$。
• 如果 $i$ 位置是房子，则 $f(i,j)= \min \{f(i-1,j+1),f(i-1,j)\}+|j|$。这里代表房子可选可不选。
• 如果 $i$ 位置是空，则 $f(i,j)=f(i-1,j)+|j|$。

最终的答案即为 $f(x,k)$。

注意到 $f(i,j)$ 对于固定的 $i$，关于 $j$ 是下凸的，很容易维护。实现中，为了方便，可以把状态改为 $f(i,j)$ 表示前 $i$ 个位置选了 $j$ 个房子的最小代价，这时最小值的位置一定是单调不降的，可以用差分维护最小值之后的斜率，对于房子只需插入一个 $0$ 的斜率。

把空的位置一起处理，就能做到 $O(m)$ 的时间复杂度。

因此，我们可以在 $O(m\log n)$ 的时间内求出最优解。

3. $n< m$ 的情况：方案数

为了计算方案数，我们还需要以下的引理：

引理 2 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。

证明 注意到对于一个全局最优解的匹配方案，每个未选择的房子 $i$ 都应该满足 $c_i=0$，即没有匹配经过该房子，否则用该房子替换这个匹配中的房子，代价严格变小。如果一个全局最优解 $S$ 在两个不同的 $k$ 处取到最优解，那么一定有一个 $k$ 使得某个未选择的房子 $i$ 满足 $c_i\ne 0$，矛盾。因此， 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。$\blacksquare$

根据引理 2，我们只需对每个 $g(k)$ 取到最小值的 $k$ 分别计算方案数并求和即可。

我们还需要以下引理：

引理 3 至多有两个 $k$ 满足 $g(k)$ 是最小值。

证明 采用反证法，假设 $g(k-1),g(k),g(k+1)$ 都是最小值。根据引理 1 的证明过程，$g(k)=\frac{g(k-1)+g(k+1)}{2}$ 的必要条件是 $c_i^{(k-1)}\cdot c_i^{(k+1)}\ge 0$（否则三角形不等式严格不等），以及对于每个极长的小数部分为 $1/2$ 的连续段，正数的个数等于负数的个数（从而无论加还是减 $1/2$，都不会改变代价）。因此不妨设 $k-1\ge 0$（$k+1\le 0$ 是对称的），找到最小的 $j$ 满足 $c_j^{(k-1)}\ne c_j^{(k+1)}-2$，则 $j$ 位置是房子。这样的 $j$ 一定存在，否则两个方案对应相同的 $S$，根据引理 2，一定不是全局最优解。此时 $c_j^{(k-1)}=c_j^{(k+1)}-3$ 或 $c_j^{(k-1)}=c_j^{(k+1)}-1$，且 $c_j^{(k-1)}\ge 0$。无论如何，我们都可以令 $c_{j}^{(k)}=c_{j-1}^{(k)}>0$，同时调整极长的连续段。但是因为 $j$ 是未选择的房子，所以这一定不是全局最优解。因此至多有两个 $k$ 满足 $g(k)$ 是最小值。$\blacksquare$

根据引理 3，我们只需要对至多两个 $k$ 分别计算方案数并求和。因此这不会增加我们的复杂度。

至于计算方案数，可以在 DP 的过程中同时进行。我们维护 DP 取到最小值的位置，并且最小值至多有两个。最小值之后的部分的方案数只需进行一个平移。因为最小值的位置单调不降，方案数也很容易维护，时间复杂度仍然为 $O(m)$。

综上，我们可以在 $O(m\log n)$ 的时间复杂度内解决该问题。

F. Magic Bean

我们只需要构造出能够交换两个环内的豆子的操作，之后每次找到 $a$ 环内的 $b$ 豆子，和 $b$ 环内非 $b$ 的豆子交换，即可在不超过 $30$ 次交换内完成复原。

构造的操作如下：把 $a$ 环内要交换的豆子移至 $1$，$b$ 环内要交换的豆子移至 $4$，$a$ 环转到 $b$ 环，$b$ 环逆时针转一格，$b$ 环转到 $a$ 环。

G. Manhattan Walk

由于每个格子的状态是均匀独立随机的，并且到一个格子之前无法得知该格子的状态，因此可以看做到每个格子时再均匀随机状态。

设 $f(i,j)$ 表示从 $(i,j)$ 开始，到达终点的期望最小时间。如果 $i=r$ 或 $j=c$，则可以直接转移，否则设两个方向的 $f$ 值分别为 $a$ 和 $b$（$a\le b$）。

讨论两种情况：

• $b\ge a+p$，那么无论如何都会选择 $b$，期望为 $a+p/4$。
• $b < a+p$，那么只有当离能走 $a$ 还有超过 $b-a$ 的时间才会选择走 $b$，期望为 $(p-b+a)/2p\cdot b+a/2+(b-a)/2p\cdot (a+b)/2$。（三项分别代表选择走 $b$、可以走 $a$ 时走 $a$、等待后走 $a$ 的期望。）

时间复杂度 $O(rc)$。

H. MountainCraft

注意到斜线的长度等于横向覆盖的长度乘以 $\sqrt 2$。而横向覆盖的长度就是所有 $[x-y,x+y]$ 的并。使用线段树维护即可（维护区间最小值和最小值个数；或者因为减法只是加法的撤销，维护每个结点的覆盖次数）。

时间复杂度 $O(q\log q)$。

I. Not Another Constructive!

我们可以在字符 A 的位置计算贡献，也就是前缀中 N 的数量和后缀中 C 的数量的乘积。因此设 $f(i,N,C,k)$ 表示考虑了长度为 $i$ 的前缀，前缀中 N 的数量为 $N$，后缀中 C 的数量为 $C$，是否能恰好有 $k$ 个 NAC 子序列。可以用 bitset 优化。

时间复杂度 $O(n^3k/w)$。

J. Passport Stamps

第 $i$ 趟旅行可能无法进行的条件是 $p\le \sum_{j=1}^{i-1}c_j+i\cdot (c_i-1)$，也就是在前面每个章之间留恰好 $(c_i-1)$ 的间隔。

时间复杂度 $O(n)$。

注意，直接计算可能会超过 long long 的范围，需要使用 __int128 或改用除法。

K. Shadow Line

注意到要判断是否只有一片影子，只需要知道每个端点在墙上的位置的相对关系。而这些相对关系只会有 $O(n^2)$ 次变化，也就是在两两的连线与 $x$ 轴交点的位置。算出这些变化的位置之后就可以进行模拟。

只有一片影子的充要条件是对于每个真前缀，下端点的数量大于上端点的数量。因为每次都是交换位置相邻的端点，因此这个条件可以在 $O(1)$ 时间内维护。

要注意的细节包括在有三点共线时的交换顺序，以及 $x$ 轴上的下端点应该始终排在上端点之前。

时间复杂度 $O(n^2\log n)$。

L. Square of Triangles

M. Training, Round 2

设 $f(i,j,k)$ 表示考虑前 $i$ 个题，是否能恰好加 $j$ 次实现水平和 $k$ 次思维水平。注意这里当某个 $(j,k)$ 能达到时，之后都能达到。因此我们对每个 $j$ 维护两个集合：已经能达到的 $k$ 的集合以及已经更新过的 $k$ 的集合。对于每个问题，我们只需找到矩形中能达到但还未被更新过的 $(j,k)$，将 $(j+1,k)$ 和 $(j,k+1)$ 都加入能达到的集合。因为每个 $(j,k)$ 只会被更新一次，所以时间复杂度是 $O(n^2\log n)$。