官方题解。来源：清华大学学生算法协会仓库

枚举平移的距离，考虑把第二张图中所有的点分成四类：

• 当前和第一张图不相等，在平移之后也不相等。
• 当前和第一张图不相等，在平移之后相等。
• 当前和第一张图相等，在平移之后也不相等。
• 当前和第一张图相等，在平移之后也相等。

最终的答案一定是由第二类点和第四类点组成的极大子矩阵。这个可以 使用全 1 子矩阵的算法计算。

第一类点必须是平移之后被随机填充的部分，如果他的坐标是 $(x,y)$，那 么 $(x,y-d)$ 必须被平移。我们可以找到一个能覆盖所有 $(x,y−d)$ 的最小 矩形，答案矩形必须包含这个矩形。

再考虑第二类点，它要么是被随机填充的部分，要么是被平移的部分。 对于一个矩阵，我们只需要求出这两块里第二类点的数量，就知道其是 否合法了。

做全 1 子矩阵，把求出的每个极大子矩阵 check 一遍即可。

官方题解。来源：清华大学学生算法协会仓库

简要题意

• 小 Rei 在 $n$ 天内每天骑共享单车，第 $i$ 天 $s_i$ 分钟，每分钟费用 $c$ 元
• 可任意购买 $m$ 种骑行卡，其中第 $i$ 种骑行卡：
• 售价为 $w_i$ 元，在有效期 $d_i$ 天内每天前 $t_i$ 分钟免费
• 同一天多张卡有效时，取免费时间的最大 $t_i$
• 求最小总开销
• 数据范围：$n,t \le 150$

区间 DP？

• 每张骑行卡会在一个区间的时间内产生影响，自然可以想到区间 DP
• 考虑最优方案中 $t_i$ 最小的骑行卡 $i$，设这张卡在第 $x$ 天购买。接着可以把 $n$ 天分成三段：$[1,x-1],\,[x,x+w_i-1],\,[x+w_i,n]$，这三段分别成为相对“独立”的子问题
• 但是独立性不一定成立：可能存在其他的骑行卡的有效时间与上述的至少两段时间都有交，这样就不是独立的子问题了

构造独立性

• 我们假设存在一个 $t_j > t_i$ 的骑行卡 $j$，其有效时间为 $[y,y+w_j-1]$，满足 $y\le x \le y+w_j-1$。此时可以舍弃卡 $i$ 与 $[y,y+w_j-1]$ 有交的部分时间而不影响答案
• 也就是只要将卡 $i$ 的有效期限定为 $\le w_i$ 的任意整数值，同时不允许后续的有效期区间跨过卡 $i$ 有效期边界，就能分成三个独立的子问题

区间 DP

• 接着就可以做区间 DP，设 $f[i][j][k]$ 表示只考虑时间 $i,i+1,\cdots,j$ 与路程中超过 $k$ 分钟的部分，最小的代价是多少。转移只需要枚举区间内的最小 $t$ 以及左右端点，就能做到 $O(n^4 t^2)$
• 为了时间复杂度与 $m$ 无关，可以预处理 $\mathrm{cost}_{i,j}$ 表示有效期为 $i$ 免费时间为 $j$ 的最少骑行卡价格

DP 优化

• 转移中需要枚举区间中的最小 $t_i$，实际上是在求后缀最大值，在加入辅助数组优化后做到 $O(n^4t)$
• 注意到转移时需要同时枚举中间区间的左右端点。我们考虑再设计一个中间状态，将转移中的枚举左右端点分成两步，就能做到 $O(n^3t)$
• 区间 DP 自带 $1/3!=1/6$ 的常数，$150^3/6\approx 8\times 10^7$ 可以在时限内通过

喜提最劣解（常数最大解）。第一遍甚至读错题一个小时，喜提视力最好奖。

不难发现题目要求除了给定的黑点外其他点不能染成黑色（就是读错在这里了）。

因此不难发现，若一个灰点周围有至少一个黑点，则这个点要满足两个条件之一。

一：这个点初始染成白色

二：这个点与一个初始染成白色的点相连。

然后就是很基础的东西了，因为相连在树上有儿子和父亲的关系，所以要分讨几种情况。

假如说将 $1,5,6$ 染成黑色，答案为 $1$，将 $3$ 染成白色即可，可以手玩一下，就知道怎么设置状态了。

设 $dp_{x,0/1/2/3}$ 分别表示 $x$ 不染成白色/染成白色/不染成白色，但保证父亲染成白色/不染成白色，但保证有至少一个儿子染成白色。

若 $x$ 是 $y$ 的父亲：需要保证 $dp_{y,2}$ 只能通过 $dp_{x,1}$ 转移。

对于至少一个儿子染成白色，先不强制限制，最后加上 $\min(dp_{y,1}-\min(dp_{y,0},dp_{y,1},dp_{y,3}))$ 做一个类似反悔的操作即可。

若 $x$ 初始染成黑色，则所有转移结束后令 $dp_{x,1}\gets \infty$，若 $x$ 周围至少有一个黑点，则所有转移结束后令 $dp_{x,0}\gets \infty$，防止传上去不合法的状态。

最后的答案是 $\min(dp_{1,0},dp_{1,1},dp_{1,3})$。时间复杂度为 $O(n)$。

感觉像是什么很复杂的博弈，应该是结论题，但是我不会猜结论。

考虑一些简单的做法，先特判掉 $n\le 3$ 的情况，因为此时一步能到达所有格子。

其他情况考虑二分答案 $mid$，判断能否得到 $\ge mid$ 的分数，这样令 $b_i=[a_i<mid]$，我们将问题转化为能否取到 $0$。

若 $b_i$ 的 $1$ 的个数 $\le 2$，因为此时 $n>3$，一定可以取到 $0$。

否则，令 $b_0=b_{n+1}=1$，若 $b_{x-1}+b_x+b_{x+1}\le 1$，则一定能取到，因为无论如何交换，第一步都能走到一个 $0$，否则则一定能控制 $b_{x-1},b_x,b_{x+1}$ 都是 $1$，必输。

然后做就行了，复杂度为 $O(Tn\log V)$。

当 $k$ 较大时

• 黑色格无三连……

  • 任意三个连续的格子中至多有两个黑色格……
  • 黑色格比例 $\le \frac{2}{3}$
• $k > \left\lfloor\frac{2}{3}n\right\rfloor$ 时无解。

构造答案

$k = \frac{2}{3}n$

$k = \frac{1}{2}n$

可见，它们可自由组合

$\left\lceil\frac{1}{2}n\right\rceil \le n \le \left\lfloor\frac{2}{3}n\right\rfloor$ 时均可构造。

目前的结论

• $k > \left\lfloor\frac{2}{3}n\right\rfloor$ 时无解。
• $\left\lceil\frac{1}{2}n\right\rceil \le n \le \left\lfloor\frac{2}{3}n\right\rfloor$ 时可通过组合基本型来构造合法答案；
• $k < \left\lceil\frac{1}{2}n\right\rceil$ 时……无解

$k < \left\lceil\frac{1}{2}n\right\rceil$ 时一定有白色格三连？

• 显然 $n$ 越大，$k$ 越小时越容易产生白色格三连，因此不妨默认 $n$ 为奇数且 $k=\left\lceil\frac{1}{2}n\right\rceil - 1$。
• 先从最基本的 $n=5, k=2$ 开始...

$n=5, k=2$

• 以下称第 $j$ 列从上至下第 $i$ 个黑色格为“第 $i$ 条链的第 $j$ 个格子”；
• 第 2 条链的格子分布？

第 1, 5 列的范围是显然的；
如果第 2 条链的第 2/3/4 个格子在第 3 行的话...

• 第 2 条链的格子分布；
• 由对称性得到第 1 条链的分布；
• 叠加？

$n, k$ 更大时？（$k=\lfloor\lceil\frac{1}{2}n\rfloor\rceil - 1$）

结论

• $k > \left\lfloor\frac{2}{3}n\right\rfloor$ 时无解。
• $\left\lceil\frac{1}{2}n\right\rceil \le n \le \left\lfloor\frac{2}{3}n\right\rfloor$ 时可通过组合基本型来构造合法答案；
• $k < \left\lceil\frac{1}{2}n\right\rceil$ 时……无解

引言

冷知识：这题曾经可能会选入今年 CTS 或者联合省选。只是因为各种各样的原因这题很早（今年一月）就没了。

其实不是一道很难的题目，思路想清楚了就非常简单了，代码也很短，最难写的地方甚至只是一个最简单情况的特判。

叫做“列队”是因为本题是因军训列队有感而出。某种意义上也是一种提示。

作为投题列表里少见的 ds 题，这题刚投就被选上了。有没有人以为这是 lxl 题？

开 5s 单纯是不想完全卡掉带 $\log$ 的做法，实际上这题只要实现优秀或者调过块长多带一点 $\log$ 都是轻松过的。

这题把大数据塞在了开头，避免卡评测太严重。

比赛情况

本题预期难度是 medium+ 到 hard。不过对于熟练的 OI 选手其实应该是 medium？

来自长郡中学的队伍 Centroid.reborn(2025) 以 5 发罚时的战绩取得了首杀，似乎是写了有着巨大常数的莫队二次离线，经过各种卡常最后以 4.67s 艰难通过了。（其实没有造极限数据，认真造的话估计可以卡到 20s）

剩下的几支队伍基本都是写巨大难写的根号分治做法的。

场上甚至没看到人写正解……

题意简述

给定一个 $n \times m$ 的排列矩阵。

维护 $q$ 次操作。查询为假设反复按行列进行排序直到某次失败，最后查询单点值；修改为交换两个数。

$1 \le n \times m \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，5s/2GB。

思路

我们先证明一个引理：排序两轮后就不可能再修改了。

为什么？我们考虑把所有小于 $w$ 的数赋值为 $0$，其余赋值成 $1$，那么排序两轮后 $0$ 就会聚集在左上角而 $1$ 就会聚集在右下角。

对每个 $w$ 都如此就意味着不会再有“逆序”存在了。

于是只用分类“一次都没成功排序”和“成功排序了 $1 \sim 2$ 次”的情况。

这只用维护有多少个行内相邻的“逆序”即可判断。而这是容易做到 $O(1)$ 维护的。

第一种情况只用维护矩阵的实际形态即可解决，难点在于第二种情况。

容易发现这样问题就变成了求各行第 $y$ 小数中，第 $x$ 小的是多少。看上去就不像能 polylog 的样子。

由于限制了矩阵总大小，容易想到根号分治类算法，但是估计很难写，所以我们换个思路。

注意到这是排列，于是我们不妨考虑对每个数维护其处于的位置，然后对这个“位置数组”进行分块。

我们现在要找到一个最小的位置 $p$，使得 $p$ 之前出现过至少 $y$ 次的行号有 $x$ 种。

于是设立间断点 $0, B, 2B, \cdots$，记录间断点之前的每种行号的出现次数，以及开桶记录每个出现次数对应了多少合法（至少这么多次数）的行号。

修改操作只用修改 $O(nm/B)$ 个间断点处的信息，每次是 $O(1)$，复杂度即为 $O(nm/B)$。

而查询操作可以先通过二分或者枚举找到答案位于哪个块，再在块内不断尝试添加单项直至合法。这部分复杂度即为 $O(\log(nm/B) + B)$。

取 $B = $Θ\Theta(\sqrt{nm})$，总复杂度即可做到 $O((nm + q)\sqrt{nm})$，可以通过此题。

std 写了 2kb，没有调过块长，跑了约 700ms。

没有特意卡带 $\log$ 的做法。

总结

题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！