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

首先，X 把整个序列分成了若干段，段与段之间是独立的。

考虑每一个不含 X 的连续段，若这个段为 MWMW，如果 W 老师操作这个段，那么他拿走 WMW 一定是不劣的，因为拿走这个之后剩下 M，M 必须花一次操作拿走，如果剩下其他的，Menji 也可以花一次拿走，相当于，我们只给 Menji 留严格更少的选择。

但考虑这样的区间 WMWMW，W 老师不可能拿的只剩一个 M。

我们可以发现，如果有这个贪心，那么一个连续段只与其两端点，以及中间是否有其他字符有关。

我们将段分为 $5$ 类，WW，WMW，MM，MWM，WM，分别表示两端为 W/M，且中间是否有另外一种，比如 WW 代表两边都是 W 且中间没有 M，WMW 表示两边都是 W 中间有 M，WM 表示一边是 W 一边是 M。

令 $w_0,w_1,m_0,m_1,c$ 分别表示这些段的数量。

$c$ 的存在是无意义的，当 W 老师操作一个 WM 段时，一定剩下一个 M，此时 Menji 直接拿走这个 M，游戏回合数不受影响，这样的操作也不会影响平局，若一方因此不能平局，其可以在游戏的最开始先操作这个 WM 段。

那此时的操作可以看成，W 老师可以一回合内让 $w_0-1$ 或 $w_1-1$ 或 $m_0-1,m_1+1$，Menji 一回合可以让 $m_0-1$ 或 $m_1-1$ 或 $w_0-1,w_1+1$。略微讨论一下，可以发现 W 老师胜利条件为 $w_0+w_1<m_0+m_1$ 或 $w_0+w_1=m_0+m_1,m_0=0$。Menji 获胜条件为 $m_0+m_1+1<w_0+w_1$ 或 $m_0+m_1+1=w_0+w_1,w_0=0$。其余都是平局。

本题的灵感来源是一个之前玩过的桌游，四人分成红蓝两队，有 $25$ 个隐藏中文词，一些属于红队一些属于蓝队一些没有归属还有一个特殊词。所有玩家能看到所有词，但两队分别有一个人能看到所有词的类型（属于哪一队或是特殊词），两队能看到词类型的玩家轮流操作，说一个简单的短语，另一名玩家可以猜任意数量的词，无论是否猜中将猜的词移除，当一个队的词全部被移除时该队获胜，特别的，如果一个队移除了特殊词，该队直接失败。

题目其实是将高维空间的词看成一维空间的点并将描述看成区间，特殊词即为 X，似乎我目前还没有想出高维空间中的解决方案（假设一个描述是一个高位立方体？），欢迎大家思考一下。

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

考虑自然的图论模型，$n$ 个点，$i$ 连向 $a_i$。如果没有 $(j-i) > 1$，显然只需要 $n$ 减环长次操作就可以排序。注意到这个排序策略必须要每一次都环数 $+1$ 才行，也就是每一次操作都在环内。

当我们不能用环长 -1 次环内的不相邻交换操作排序，我们就称这个环是难的。认为自环不是难的，这样最终状态没有难的环。显然编号相邻的二元环是难的，所以有难的环。考察什么样的环是难的。

如果一个环在编号上占据的不是一段区间，那么它不是难的：假设存在一个 $l$ 不在环上且有 $>l$ 和 $<l$ 的点在环上，那么必然存在一条 $<l$ 到 $>l$ 的边，也存在一条 $>l$ 到 $<l$ 的边。任选其中一条边交换，可以让 $<l$ 或者 $>l$ 的点的个数减 1 并获得一个自环。一直做直到两边都剩一个点，这个时候交换它们俩就行了。

考虑值域连续的环，设其长度为 $l$。注意到若存在一个 $i \in [2,l-1]$ 它的位置不是 $i-1$ 或者 $i+1$，就可以通过把 $i$ 归位创造一个长度为 $(l-1)$ 的值域不连续的环。因此这样的环不是难的。

所以难的环一定有 $i \in [2,l-1]$ 的位置要么是 $i-1$ 要么是 $i+1$，即可以选左右。注意到若 $p$ 选右 $p+1$ 选左就会有二元环不符合这个环长条件，所以一定是一段前缀选左一段后缀选右，所以环长成 2 3 4 5 ... k n 1 (k+1) (k+2) ... (n-2) (n-1) 这个样子。

当这个环不是 2 3 4 5 ... (n-1) n 1 的时候，你总是可以通过归位最小或最大元素，把这个环归位成 2413，此时存在一个三步的做法：交换 23 之后交换 24 和 13。

而当这个环是 2 3 4 5 ... (n-1) n 1 的时候，我们归纳证明其是难的。$n=2$ 显然是难的，因为交换不了。对于更大的 $n$，任意交换环上的两个元素会得到两个环，而之后必须要两个环都不是难的才能在 $n-1$ 次操作内排好序。但注意到交换了 $a_i=(i+1)$ 和 $a_j$ 之后，$a_{i+1} \sim a_j$ 就是 $i+2\ i+3\ \cdots\ j\ i+1$ 恰好构成一个长度为 $j-i \ge 2$ 的由归纳假设是难的环。所以第一步怎么做最后都会有一个难的环，所以这个环也是难的。

对于不难的环我们直接排到对应位置，对于难的环我们不能直接排好，需要用一些额外的操作来搞定。因为一次把两个环合并成一个，会导致总步数+2，同时最多删掉两个难环，因此答案下界是 $n$ 减环数加上（难环数量除 2 上取整乘二）。

这个下界是容易达到的：先把所有难环都弄成二元环，简单环排好，然后对于 2143，先交换 23 得到 3142，这个环不是难的，直接弄就行了。单独剩下一个 12 的情况，$n \ge 5$ 的时候总可以找到一个不相邻的位置，用三步操作归位。$n \le 4$ 的情况需要特判，小点全都暴力就行了。

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

操作顺序无关。一堆积木操作后会变成一段或两段连续的 $1$。两个这样的东西合并还是会变成一段 $1$ 被挖掉一个空的形状。

注意到操作前后坐标和不变，所以可以直接算出最后的位置。

由于 $x_i$ 已经排好序了，可以使用栈进行合并。

询问的时候也是从左到右扫一遍，时间复杂度 $O(n)$。

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

$H$ 的数据范围暗示，需要高效的算法来确定分界值 $u^*$。由于分界值 $u^*$ 和划分出的席位数（即 $u_i/2^j \ge u^*$ 的 $(i,j)$ 对数）之间具有良好的单调关系，可以用二分 $u^*$ 的办法求解。

每次二分 $u^*$，对每个 $u_i$ 判断可以分得多少席位。整理不等式可得

$$j \le \log\frac{u_i}{u^*}$$

故可以分得 $\left\lfloor\log(u_i/u^*)\right\rfloor$ 个席位。对每个 $u_i$ 可以 $O(1)$ 求解（假设忽略运算复杂度），则总复杂度为 $O(T\log H)$，可以通过本题。

直接对 $u^*$ 二分，可能会出现很大的精度问题：每个 $u_i$ 最少分得 $H/T$ 个席位，故

$$u^* \approx \frac{u_i}{2^{H/T}} \rightarrow 0$$

一种解决办法是，对 $v^*=\log u^*$ 进行二分，则可以转化为 $j = \left\lfloor\log u_i − v^*\right\rfloor$，相对而言精度问题不大。

更进一步地，可以对 $v^*$ 的整数部分和小数部分分开求解。整数部分需要根据是否大于 $\left\lfloor\max\log u_i\right\rfloor$ 简单讨论，小数部分直接排序即可。这样可以完全避免精度问题。

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

$n\leq 2$ 的情况可以特判。

可以发现，任意时刻，如果 The BOT 在位置 $x$，那么可以移动到相邻位置之一，无论 The NIT 怎么操作，The BOT 至少可以得到相邻位置的次小值并结束。

另外，当 $n\geq 3$ 时，可以先走到一个 $1<x<n$ 的位置，此时一定可以有三个选项。所以至少可以获得全局的第三小值。

于是一个答案的下界就是 $\max($相邻位置次小值，全局第三小值$)$，容易发现这也是一个上界，如果答案更大，那么将小于答案的看成 $0$，大于等于的看成 $1$，那么全局有 $\geq 3$ 个 $0$，且初始与位置相邻的位置至多有一个 $1$，The NIT 始终可以把一个 $0$ 交换过来，使得 The BOT 周围的三个数都是 $0$。

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

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

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

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

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

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

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