引言

冷知识：这题曾经可能会选入今年 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$ 的做法。

总结

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