The 4th Universal Cup. Stage 13: Grand Prix of Ōokayama（无 EL）

关于 E：会有的。

A. Depth of Interval

经过感受，一个猜测是在递归一次后可能的区间数量并不多。

考虑从值小到大加入序列，当加入下标 \(i\) 时，考虑其左侧 \(2\) 个已加入的下标和右侧 \(2\) 个已加入的下标，记为 \(l_2, l, i, r, r_2\)。

那么会发现递归一次后不会存在 \([l_2, i]\) 这个区间，因为 \(a_{l} < a_{i}\)，所以每次加入 \(i\) 至多只会产生 \(2\) 个区间：\([l, i], [i, r]\)。

并且可以知道递归一次后为 \([l, i]\) 的区间数即为 \((l - l_2)(r - i)\)，因为若包含了 \(l_2\) 或 \(r\) 最后的区间都不会取到 \(i\)，且该区间必须包含 \([l, i]\)，同理递归一次后为 \([i, r]\) 的区间数为 \((i - l)(r_2 - r)\)。

那么这就已经把所有区间归到了这 \(\mathcal{O}(n)\) 个区间上了，只需要处理这些区间的递归关系即可。

此时递归关系很好刻画，例如 \([l, i]\) 这个区间，就是当 \((l, i)\) 中加入两个下标时，递归到的区间就是这两个下标对应的区间。
考虑在加入新区间的时候处理递归到其的区间，发现也就是若 \([l_2, r]\) 是一个合法的区间，那么其递归后就会是 \([l, i]\)，同样的 \([l, r_2]\) 递归后会是 \([i, r]\)。

用 set 和 map 处理就可以做到 \(\mathcal{O}(n\log n)\)。

submission。

B. Increasing Swaps

这个 \(t\ge T_i\) 的就像是个“激活”操作。

一个时刻激活的极长连续段 \([l, r]\) 操作后就相当于是 \([l, r + 1]\) 循环左移一位。

于是此时至少有一个类似插入排序的想法，就是只激活 \([1, i]\) 并始终保证 \([1, i + 1]\) 循环必定存在一个断点使得断开是正向有序的，就可以一直转圈直到 \([1, i + 2]\) 也满足该条件然后去激活 \(i + 1\)。

根据这个过程，会发现激活的极长连续段应当是要保证存在断点正向有序的，因为无序的段插入一些元素也不会变得有序。

于是有一个 \(\mathcal{O}(n^3)\) 或是 \(\mathcal{O}(n^4)\) 的区间 dp 是设 \(f_{l, r, i}\) 为区间 \([l, r]\) 以排好序且 \(i\) 为头的最小时刻，转移可以枚举割点然后两侧取 \(\max\)。

刚刚的想法的问题是过程中考虑的是合并，但是合并就存在很多时刻和状态不好处理。
于是考虑逆序操作，令 \(p\gets p^{-1}\)，那么操作变为可以“关闭”一个 \(i\)，每个激活的极长连续段操作后就是循环右移一位。

那么此时就有个很显然的贪心了：考虑一直循环右移，若这个序列能被分裂成 \(\ge 2\) 段，其中每列的值域是连续的，那么直接分裂即可。

这个正确性很好说明，因为如果当前能分裂却要等到之后再分裂，那么此时分裂后一定能在之后的那个时刻之前分裂出更碎的段。

时间复杂度 \(\mathcal{O}(n^2)\)。

submission。

C. Sum of Three Inversions

通过数据范围推测这题需要做到 \(\mathcal{O}(n^5)\)，那么直接大力记录许多信息的 dp 是不好优化下去的。

考虑回到 \((a_i, b_i, c_i)\) 为 \(\{1, 2, 3\}\) 排列的性质，这启发不去独立开 \(a, b, c\) 各自的逆序对而是转而考虑两两排列的逆序对贡献。

此时可以把 \(3! = 6\) 种排列构成的二元组产生的逆序对数算一下，会发现以下事实：

• 若两个排列相同，则不会产生逆序对，否则至少产生 \(1\) 个逆序对。
• 只有 \([1, 2, 3]\to [3, 1, 2]\to [2, 3, 1]\to [1, 2, 3]\) 和 \([1, 3, 2]\to [3, 2, 1]\to [2, 1, 3]\to [1, 3, 2]\) 这 \(6\) 个箭头代表的对会产生 \(2\) 个逆序对。

于是可以把贡献改为所有不同的对都会贡献 \(1\)，同时再去计算能产生 \(2\) 个逆序对的对数相加（相当于是统计了 \(\ge 1, \ge 2\) 的数量）。

因为本题正好给出了 \(X, Y, Z = N - X - Y\) 分别代表 \(p_1\) 分别为 \(1, 2, 3\) 的数量，那么每种 \(p_1\) 枚举其两个排列中的一个排列的数量，就可以在 \(\mathcal{O}(n^3)\) 的复杂度内枚举出 \(6\) 个排列各自的数量，那么 \(\ge 1\) 的对的数量就统计出了。

接下来考虑逆序对数 \(= 2\) 的排列对，根据刚刚的分讨，能发现其实能把 \(6\) 个排列分为 \(2\) 组，每组内 \(3\) 个排列，只有这 \(3\) 个排列间可能产生 \(2\) 个逆序对。

并且能够发现这 \(3\) 个排列都分别是 \(1, 2, 3\) 开头的，且开头 \(1\to 3\to 2\to 1\) 会产生 \(2\) 个逆序对。
于是直接设计 dp 为 \(f_{x, y, z, i}\) 表示一组内开头为 \(1, 2, 3\) 的排列分别有 \(x, y, z\) 个且逆序对为 \(2\) 的数量有 \(i\) 个，转移直接枚举下一个排列的开头即可，就能做到 \(\mathcal{O}(n^5)\)。

到最后算贡献的时候，因为已经知道了 \(6\) 个排列各自的数量，这里按照组和开头分别记为 \((x, y, z), (x', y', z')\)，也知道了已经产生的贡献 \(w\)。
然后要让 \((x, y, z), (x', y', z')\) 的贡献和加上 \(w\) 恰好为 \(k\)，于是对答案的贡献可以表示为 \(\binom{n}{x + y + z}\sum\limits_{i + j + w = k} f_{x, y, z, i} f_{x', y', z', j}\)，那么直接枚举 \(i\) 就是 \(\mathcal{O}(n^2)\) 的，结合外层的枚举 \(x, y, z\) 就是 \(\mathcal{O}(n^5)\) 的。

最后复杂度 dp 和最后的求值都为 \(\mathcal{O}(n^5)\)。

submission。

这样看来这或许也是一个平衡的想法？因为直接大力 dp 的 dp 复杂度会很大，但最后查值的复杂度时较小的，于是尝试在查值的时候去多枚举一些变量减少 dp 记录的元素数以平衡复杂度。

D. Grid Path Tree

首先关注这个连边的过程，发现这能和网格图路径一一对应。

如下图所示：

考虑一个网格图上只能向上和向右的 \((1 ,1)\) 起 \((n, m)\) 终的路径，编号为 \([1, n]\) 的点就对应横坐标为 \([1, n]\) 的竖线，编号为 \([n + 1, n + m]\) 的点就对应竖坐标为 \([1, m]\) 的横线，路径上的每个点 \((i ,j)\) 就代表给第 \(i\) 条竖线和第 \(j\) 条横线连了一条边。

首先不妨认为 \((1, 1)\) 之后的下一步就是 \((1, 2)\)，如果不是，那么交换 \(n, m\) 处理即可。

记 \(Dx\) 表示向 \(D\in \{\text{R}, \text{U}\}\) 这个方向走了 \(\ge x\) 步，那么这个路径可以被刻画为 \(\text{R}1, \text{U}1, \text{R1}, \text{U1}, \cdots\) 这样的路径序列，最后结尾既可以是 \(\text{R}1\) 也可以是 \(\text{U}1\)，视这个序列长度而定，还需要保证的是 \(\text{R}, \text{U}\) 最后走的总部数需要分别为 \(n - 1, m - 1\)。

接下来考虑把 \(\operatorname{dist}(i, j) = k\) 这个条件放在网格图上刻画。

玩一下的话发现要按照 \(k\) 的奇偶分讨：

• 当 \(k\) 为奇数时，\(k = 1\) 比较特殊，方案数容易知道 \(\binom{n + m - 2}{n - 1}(n + m - 1)\)。

  先假设 \(k = 3\)，下图中的蓝色直线与绿色直线就是满足条件的对：

  

  考虑把上图中的每一对合法的蓝绿直线都在路径上对应的位置截断，再转成路径序列，会发现都对应着 \({\color{red}\text{R}0}, \text{R}1, \text{U}1, {\color{red}\text{U}0}, \text{R}1, \text{U1}, \text{R}1\cdots\)。
  同时，会发现 \(\text{R}1, {\color{red}\text{U}0}, \text{U}1, \text{R}1, {\color{red}\text{R}0}, \text{U1}, \text{R}1\cdots\)，\(\text{R}1, \text{U1}, {\color{red}\text{R}0}, \text{R}1, \text{U}1, {\color{red}\text{U}0}, \text{R}1\cdots\) 也都对应着 \(k = 3\) 的合法对。

  可以继续手玩扩展到 \(k\) 更大的情况，发现合法路径序列一定可以以如下方式生成：

  • 首先得到一个长度为 \(L\) 的一般路径序列：\(\text{R}1, \text{U}1, \text{R1}, \text{U1}, \cdots\)。
  • 选择 \(i\) 满足 \(i\ge 1, i + k - 2\le L\)，在序列的第 \(i\) 项前插入 \(\color{red}D_{i}0\)，在序列的第 \(i + k - 2\) 项后插入 \(\color{red}D_{i + k - 2}0\)。

  然后考虑对于这个路径序列计数。

  首先一般路径序列一定会有恰好 \(\lceil L / 2 \rceil\) 个 \(\text{R}1\)，恰好 \(\lfloor L / 2 \rfloor\) 个 \(\text{U}1\)。
  其次会发现 \(i\) 和 \(i + k - 2\) 奇偶性是不同的，所以一定有恰好 \(1\) 个 \(\color{red}\text{R}0\) 和 \(1\) 个 \(\color{red}\text{U}0\)。

  对 \(\text{R}, \text{U}\) 分别用插板法计数，可以得到分别的方案数为 \(\binom{n - 1}{\lceil L / 2 \rceil}, \binom{m - 1}{\lfloor L / 2 \rfloor}\)，再乘上选择 \(i\) 的方案数 \(\max(0, L - k + 2)\) 即为固定 \(L\) 时对 \(k\) 的答案的贡献。

• 当 \(k\) 为偶数时，会发现合法路径序列的生成方式其实与奇数是相同的。

  此时唯一的一个不同点是 \(i, i + k - 2\) 奇偶相同的，所以增添的元素会是 \(2\) 个 \(\color{red} \text{R}0\) 或者 \(2\) 个 \(\color{red}\text{U}0\)。

  再度分讨即可：

  • 若增添了 \(2\) 个 \(\color{red}\text{R}0\)，那么方案数为 \(\binom{n}{\lceil L / 2 \rceil + 1}\binom{m - 2}{\lfloor L / 2\rfloor - 1}\max(0, \lceil L / 2\rceil - k / 2 + 1)\)。
  • 若增添了 \(2\) 个 \(\color{red}\text{U}0\)，那么方案数为 \(\binom{n - 2}{\lceil L / 2 \rceil - 1}\binom{m}{\lfloor L / 2\rfloor + 1}\max(0, \lfloor L / 2\rfloor - k / 2 + 1)\)

若枚举 \(L\)，此时就有了个 \(\mathcal{O}(n^2)\) 的做法。

优化到线性是容易的，考虑如果固定 \(L\) 和 \(k\) 的奇偶性，那么每个方案数的前两个组合数的乘积 \(v\) 是定值，后面一个式子都是 \(\max(0, L - k)\) 这样的形式，那么找到合法的 \(k\) 的区间（应当是一个前缀后），用差分前缀和维护 \(\sum vL, \sum v\) 即可。

时间复杂度 \(\mathcal{O}(n)\)。

注意特判 \(n = 1\) 或 \(m = 1\) 的边界情况（此时组合数的上下标可能会出现 \(-1\)）。

submission。

F. Decimal Pyramid

考虑从底至顶标号为 \(0\sim n - 1\)。

直接合并复杂度不可接受，考虑从顶到底递推出每个位置对最终答案的贡献。

记 \(f(i, j)\) 为 \(i\) 行 \(j\) 列对答案的贡献，转移即为 \(f(i, j)\to f(i - 1, j + 1), f(i, j)\times 10^{2^i}\to f(i - 1, j)\)。

发现 \(i\) 行对 \(i - 1\) 行的递推式子都是相同的，于是写为多项式。
记 \(F_i(x) = \sum\limits_{j = 0}^{n - i - 1}f(i, j)x^j\)，有 \(F_{i - 1}(x) = F_i(x) \times (10^{2^i} + x)\)，分治 NTT 即可解决。

最终答案即为 \(\sum\limits_{j = 0}^{n - 1} f(0, j)s_j\)。

时间复杂度 \(\mathcal{O}(n\log^2 n)\)。

submission。

G. Don’t Make Zero

发现 \(X\) 和 \(N\) 的量级差距其实比较大，于是一个想法就是给所有数都用上一个足够大的偏移值，使得大小关系基本可以由偏移值操控。

于是一个想法就是从 \(N - X + 1, \cdots, N - 1, N\) 这 \(X\) 个数中选，同时因为不希望正负相同的数量会出现相同的和，于是考虑直接构造为 \(-\) 用前 \(cnt(-)\) 个数，\(+\) 用前 \(cnt(+)\) 个数。

那么这样首先当 \(+\) 选取的数量不比 \(-\) 选取的数量时，最后带符号总和肯定是个正数。

不过当 \(-\) 选取的数量更多时，因为 \(-\) 选的数值更小，所以需要仔细检查下。
考虑若 \(+\) 选了 \(c\) 个，\(-\) 选了 \(c + 1\) 个，那么 \(\sum \le \sum\limits_{i = 1}^c (N - i + 1) + \sum\limits_{i = 1}^{c + 1} (X - N - i) = (c + 1)(X - c) - N - 1\)，当 \(c = \frac{X - 1}{2} = \lfloor\sqrt{N}\rfloor - 1\) 时取到最大值 \(\lfloor\sqrt{N}\rfloor^2 - N - 1 \le -1\)。
那么若 \(-\) 选得更多只会负更多，这说明若 \(-\) 选的比 \(+\) 多是带符号和一定为负数。

所以这个策略一定是正确的。

对于构造只需要从两个端点往里取即可。

H. Akari Counting

因为对网格的改变只有染黑中间一块矩阵，这启发直接把横纵坐标拆成 \([1, A), [A, B], (B, W]\) 和 \([1, C), [C, D], (D, W]\) 这 \(3\) 个部分，也就对应把矩阵切成了 \(9\) 块。

搬一个官方题解的图：

考虑 A 块合法的条件，分为两种：

• \(e + a + f = h_1\)，也就是是行覆盖完了。
• \(e + a + f \not = h_1, a = w_2\)，也就是是行没覆盖完但列覆盖完了。

BCD 块和 A 块的合法条件是类似的。

考虑 E 块的合法条件，也分为两种：

• \(e + a + f = h_1\)，也就是行覆盖完了。
• \(e + b + g = w_1\)，有 就是列覆盖完了。

FGH 的合法条件和 E 也是类似的。

8 个条件太多了，于是尝试合并一些条件。
考虑较为“等价”的 4 个角 EFGH，如果要都合法需要满足以下两个条件至少一个：

• \(e + a + f = h_1\) 且 \(g + c + h = h_3\)。
• \(e + b + g = w_1\) 且 \(f + d + h = w_3\)。

这样做完，会发现条件 1 只与两个行（EAF，GCH）有关，条件 2 只与两个列（EBG，FDH）有关，那么行列就近似被独立开了。

但是会发现不能完全独立开，这是因为 EFGH 中会有一些灯，这是在行列合并时需要被考虑到的，于是就需要信息记录这些灯的信息了。

但单独的记录下 EFGH 各自选的灯数肯定是不可接受的。
考虑把 EFGH 拼在一起看作一个大的矩阵，如果知道了 \(i\) 个点的行和 \(i\) 个点的列的集合，那么就有 \(i!\) 的方案数（行列对应匹配）。

于是考虑对于行求出 \(f_{0/1, i}\) 分别表示满足条件 1 和不满足条件 1 时 EFGH 选出 \(i\) 个行的方案数，同样的对列求出 \(g_{0/1, j}\) 分别表示满足条件 2 和不满足条件 2 时 EFGH 选出 \(j\) 个列的方案数，答案就可以表示为 \(\sum\limits_{i} (f_{0, i}g_{0, i} + f_{1, i}g_{0, i} + f_{0, i}g_{1, i})i!\)。

\(f, g\) 的求解是相似的，于是这里只考虑 \(f\)。

发现条件 1 中的第一条 \(e + a + f = h_1\) 其实和 A 的合法条件很相似。
具体来说，如果 A 的合法条件是“行覆盖”就满足该条件，如果是“列覆盖”就不满足。
类似的，如果 C 的合法条件是“行覆盖”就满足 \(g + c + h = h_3\)，如果是“列覆盖”就不满足。

这启发继续把 \(f\) 的求解拆为 AC 两部分分别求解再合并。

具体来说，考虑记 \(x_{0/1, i}\) 表示 A 是“行覆盖”/“列覆盖”且 EF 选了 \(i\) 个灯的方案数，同样记 \(y_{0/1, j}\) 表示 C 是“行覆盖”/“列覆盖”且 GH 选了 \(j\) 个灯的方案数。
因为只有 AC 都是“行覆盖”是行的条件才合法，所以有 \(x_{0, i}y_{0, j}\to f_{0, i + j}\)，其余的都不合法，于是有 \(x_{0, i}y_{1, j} + x_{1, i}y_{0, j} + x_{1, i}y_{1, j}\to f_{1, i + j}\)。
这是一个卷积形式，于是可以 NTT 做到 \(\mathcal{O}(n\log n)\)。

接下来就只需要考虑求解 \(x_{0/1, *}, y_{0/1, *}\) 了，这也是类似的，所以这里就只考虑 \(x_{0/1, *}\)。

• 对于 \(x_{0, i}\)，那么就要求 A 中要选 \(h_1 - i\) 个灯，且行总共要选 \(h_1\) 个灯，故为 \(\binom{h_1}{i}\binom{w_2}{h_1 - i}(h_1 - i)!\)（分别代表 A 中的行，A 中的列，A 中行列配对的方案数）。
• 对于 \(x_{1, i}\)，此时 A 中明确是 \(w_2\) 个灯，那么行总共就要选 \(w_2 + i\) 个灯，故为 \(\binom{h_1}{w_2 + i}\binom{w_2 + i}{w_2}w_2!\)（分别代表选出有灯的行，A 中的行，A 中行列配对的方案数）。

于是这部分都可以 \(\mathcal{O}(n)\) 得到。

最终复杂度 \(\mathcal{O}(n\log n)\)。

submission。

I. Subgrid Connected Components

直接数连通块数比较困难，考虑用其他变量表示连通块数。

一个想法就是，对每个连通块跑出一个生成树，那么每个生成树都会满足 \(v - e_T = 1\)。
又因为 \(\sum v = V\) 是已知的，所以只需要求出 \(\sum e_T\)。

但 \(\sum e_T\) 也不好求，但是考虑到 \(\sum e = E\) 也是已知的，于是考虑去求 \(E - \sum e_T\)，也就是非树边的个数。

考虑其对偶图，会发现树边不会影响其连通块数，而每有一条非树边就会使连通块数 \(+1\)。

而初始状态就为 \(1\) 个连通块，假设现在有 \(A\) 个连通块，就可以知道 \(E - \sum e_T = A - 1\)，得到 \(\sum e_T = E - A + 1\)，则连通块数 \(C = V - E + A - 1\)。

\(V, E\) 都是好求的，\(V\) 是矩阵大小，\(E\) 可以用二维前缀和处理，此时的问题是如何求出 \(A\)。

每次暴力求出 \(A\) 肯定是不行的，于是尝试先求出整个图的对偶图连通块形态，再分析一下范围被缩减成一个矩阵时对偶图连通块的变化。

能够发现，原图中对偶图的一个连通块本身就被这个矩形所包裹，那么其形态依然不变；特殊的是如果这个连通块可以通过举行的边界连到外部，那其应该与外部合并成一个连通块。

不过因为受影响的连通块必定过边界，所以个数是 \(\mathcal{O}(n)\) 的，只需要枚举边界并检查其连通块是否会从该边界连出去即可。

不过此时还有个问题是如何统计完全被包裹的连通块数，这其实只需要选中一个代表元做二位前缀和就好了。
引入了这个后，前文也就有了一点小问题，就是在判断边界的连通块时，若其代表元本身就在矩形外，就代表着本来就认为这个连通块和外部连通，不需要对 \(A\) 付出 \(-1\) 的代价。

时间复杂度 \(\mathcal{O}(n^2 + qn)\)。

submission。

J. Divide Polygon

submission。

考虑刻画出这个划分的结构，一个想法就是考虑类对偶图。

贴一下官方题解的图：

钦定跨过 1-2 这条边的多边形内部区域为根，当作一个有根树处理。

多边形其余的 \(n - 1\) 条边就相当于一个叶子，而内部区域的 \(k + 1\) 条边就是非叶子节点。

接下来就来考虑加上限制，考虑每个区域的点，若其每一条边都会对应多边形上的一条边（对于根，可以认为根也有一条连出 1-2 这条边的边），那也就是满足 \(\deg_u \in S\)，那也就是其儿子个数 \(+1\) 要是 \(S\) 中的数。

接下来考虑把树转换成序列，一个想法就是按 dfs 序考虑。

考虑当前有个变量 \(c\) 表示还没有确定好的点数，每次取出最靠前的一个还没确定的点，分讨其类型：

• 叶子节点。则删掉该点，\(c\gets c - 1\)。
• 非叶子节点。则其有 \(x(x + 1\in S)\) 个儿子节点，把该点替换成这 \(x\) 个儿子节点，\(c\gets c + x(x + 2\in S)\)。

直到考虑完最后一个叶子，此时 \(c = 0\)，在此之前，因为每次都需要取出一个节点，所以 \(c\ge 1\)。

考虑让所有时刻的 \(c\) 都 \(-1\)，那么可以抽象为如下序列 \(a_{n + k}\)：

• 有 \(n - 1\) 个元素满足 \(a_i = -1\)。
• 有 \(k + 1\) 个元素满足 \(a_i + 2\in S\)。
• \(\sum\limits_{i = 1}^{n + k}a_i = -1\)。
• \(\forall i\in [1, n + k), \sum\limits_{j = 1}^i a_j \ge 0\)。

考虑 \(\sum\limits_{i = 1}^{n + k} a_i = -1\) 和 \(\forall i\in [1, n + k), \sum\limits_{j = 1}^i a_j \ge 0\) 这两个条件，在前面一个条件成立的情况下，可以考虑画出折线图，会发现在循环移位下只有恰好 \(1\) 种方式满足后一个条件（官方题解称作 Bertrand’s ballot theorem）。

这说明只要知道了前 3 个条件的合法序列数量，\(/ (n + k)\) 后就是最后的答案了。

用生成函数刻画，记 \(F(x) = \sum\limits_{i\in S} x^{i - 2}\)，那么对于一个 \(k\)，满足前 3 个条件的合法序列数就是 \(\binom{n + k}{n - 1}[x^{n - 2}]F^{k + 1}(x)\)。

对所有 \(0\le k\le n\) 求出 \([x^{n - 2}]F^{k + 1}(x)\)，这就是 Power Projection 问题，可以在 \(\mathcal{O}(n\log^2 n)\) 的复杂度内完成。

submission。

Power Projection

引入形式变量 \(y\)，那么要求的就是 \([x^{n - 2}]\frac{1}{1 - yF(x)}\)，这里不妨简化为求出 \([x^{n}]\frac{P(x, y)}{Q(x, y)}\)。

考虑 bostan-mori：

• \(n = 0\) 时，直接提取 \([x^0]P(x, y), [x^0]Q(x, y)\)，做除法即可。
• \(n > 0\) 时，考虑变化为 \([x^n]\frac{P(x, y)Q(-x, y)}{Q(x, y)Q(-x, y)} = [x^n]\frac{P_0(x^2, y) + xP_1(x^2, y)}{Q'(x^2, y)}\)，此时可以根据 \(n\) 的奇偶，递归至 \([x^{\lfloor n/2\rfloor}]\frac{P_{n\bmod 2}(x, y)}{Q'(x, y)}\) 求解。

虽然每递归一层 \(y\) 的指数就会翻倍，但是注意到每一层 \(P(x, y), Q(x, y)\) 中 \(x\) 的指数大于该层的 \(n\) 的项都是无用的，所以每递归一层 \(x\) 的指数也会减半，每一层的二维多项式项数都是 \(\mathcal{O}(n)\) 的，做 \(\mathcal{O}(\log n)\) 轮卷积的复杂度就是 \(\mathcal{O}(n\log^2 n)\)。

K. Two-Way Communication

因为不是最小值的那侧也要传最小值，所以传输另一个值 \(64\) 位肯定是必用的，就还剩下 \(12\) 位来做比较的工作。

因为 \(12\) 位看起来是有点少的，所以想法就是分块，每次直接传一个块的值，然后判断两侧是否能比出大小，如果能比出就传输信息，否则进入下一个块。

细致的考虑一下对于一个长为 \(l\) 的块需要多少次额外操作，首先让 A 传 \(l\) 长度（这个不算入额外操作）然后 B 作比较：

• 如果相同可以返回一个 1，用 \(1\) 次额外操作。
• 如果不同，首先就要返回个 \(0\)，然后至少需要把 B 的 \(l\) 长度传过去，发现 B 传过去后 A 其实也能直接比较出谁大谁小，故不需要单独传输一个 0/1 表示大小关系，只需要 \(l + 1\) 次额外操作。

那么块的大小就很显然了，第一个块可以分配 \(\le 11\) 的长度，第二个块因为已经用掉一次额外操作，只能分配 \(\le 10\) 的长度。
以此类推，因为总共只有 \(64\) 位，一个合法的块长方案是 \([11, 10, 9, 8, 7, 6, 5, 4, 3, 1]\)。

submission。

M. Many Approaches

首先考虑第 1 类询问。

形式化的表示一个人经过 \(X_i\) 后的位置变化可以用分段函数：\(f(x)_i = \begin{cases}x + 1 & x < X_i\\ x & x = X_i\\ x - 1 & x > X_i\end{cases}\)。

考虑继续叠加，例如记 \(g(x) = f(f(x)_i)_{i + 1}\)，会发现 \(-2\le g(x) - x\le x\)，且 \(g(x) - x\) 应当是关于 \(g(x)\) 不增的。

这说明此类函数嵌套 \(m\) 层后，每个 \(x\) 与最终位置 \(x'\) 满足 \(x' - x\in [-m, m]\)，且 \(x\) 增大的途中，\(x' - x\) 不增，那么这就是个 \(\mathcal{O}(m)\) 段的分段函数，使用线段树维护，询问只需要在 \(\log\) 个分段函数上二分即可。

接下来考虑第 2 类询问。

考虑起始位置 \(x < y\)，则最终位置一定有 \(x'\le y'\)，这说明最终位置在一个点的起始位置一定是一段区间，找到其左右端点即可。

那么只需要倒着维护左右端点 \(l, r\)，每次经过一个 \(X_i\) 其变化也可以看作分段函数：\(fl(l)_{i} = \begin{cases}l - 1 & l\le X_i \\ l + 1 & l > X_i \end{cases}, fr(r)_i = \begin{cases}r - 1 & r < X_i\\ r + 1 & r \ge X_i \end{cases}\)。

还是和上面一样的分析，嵌套 \(m\) 层后只会是 \(\mathcal{O}(m)\) 段的分段函数，同样线段树维护询问二分即可。

这里其实有个小问题是 \(l, r\) 需不需要随时都卡在 \([1, n]\) 这个范围内。
其实可以把初始位置扩充为 \((-\infty, +\infty)\)，只是最后只保留 \([1, n]\) 中的部分。
所以在过程中不需要关心 \(l, r\) 与 \(1, n\) 的大小关系，只需最后让 \([l, r]\) 与 \([1, n]\) 取交即可。

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

我觉得我的分段函数合并写的有点问题，似乎要合并相同差值的连续的段才能保证段数是线性的，但是我没有合并也过了？？？

submission。