2160A MEX Partition
这题是一道结论题。
观察到当原序列没有 $0$ 的时候，答案一定是 $0$。
观察到当原序列存在 $0$ 的时候，答案就是原数组的 $\operatorname{MEX}$，
因为没有更小的值使其 $\exists$ 一种划分，使得每个子数组的 $\operatorname{MEX}$ 相同。
Contest Submission
2160B Distinct Elements
这一题的关键是一定存在一种解。如果一定存在，我们就可以直接构造了。
详细解释一下，考虑每一次加入 $a_i$ 后和之前重复的数目 $\Delta b_i = i - (b_i - b_{i-1})$，如果我们令 $ a_i = \begin{cases} a_{\Delta b_i} &(\Delta b_i > 0) \\ \texttt{++tot} &(\Delta b_i = 0) \end{cases} $ 的话，$ f(a[1,1]), \dots, f(a[1,\Delta b_i])$ 就会有一个重复，换言之，它们的值不增加。
而这题又一定保证有解，所以不用担心出现 $\exists\, p>\Delta b_i,\; a_p=a_{\Delta b_i}$ 的情况。
Contest Submission
2160C Reverse XOR
这题是一个。。。找规律？的题。
赛时找到规律了，但就是犯唐，位数处理不够，不开 long long，然后直接挂掉。
规律很简单，就是在 $n$ 的二进制形式中，两边除去 $0$（或者你想成加上任意多个 $0$ 也行）后一定是一个回文串，而且如果长度为奇数，那么最中间的数位不能是 $1$。
什么玩意啊？！tnnd耍我呢！
事实上，这题可以这样想：
假设我随机弄了一个 $ x=(\overline{a_6a_5a_4a_3a_2a_1a_0}){\texttt{B}} $，计算 $f(x)=(\overline{a_0a_1a_2a_3a_4a_5a_6}){\texttt{B}}$。
$$
\begin{array}{c}
&&(\overline{a_6a_5a_4a_3a_2a_1a_0}){\texttt{B}} & x \\
&\operatorname{XOR} &(\overline{a_0a_1a_2a_3a_4a_5a_6}){\texttt{B}} & f(x) \\
\hline
&= &(\overline{x_0x_1x_20x_2x_1x_0})_{\texttt{B}} &x \oplus f(x)
\end{array}
$$
我们发现，因为 $a_0 \operatorname{XOR} a_6 = a_6 \operatorname{XOR} a_0, \cdots$，所以事实上 $x \operatorname{XOR} f(x)$ 左右两边是相等的（这里左右位数是以 $x$ 为基准的）。我们又发现，无论如何，$x \operatorname{XOR} x=0$，所以如果是奇数位，中间一定是 $0$。证毕！
Practice Submission
2160D MAD Interactive Problem
这题，是真的非常，非常巧妙！
让我们想一件事情，假如现在我已经有了一个下标集合 $S$ 并且 $\forall \{p,q\} \subset S, \;a_p \ne a_q $，那么此时我们在 $S$ 中加入一个新元素 $x(x \notin S)$ 并询问这个集合的 $\texttt{jury}$，并且我们得到了一个 非 $0$ 的返回 $q$，那么说明什么？？
说明！$a_p=q$！是不是？因为前面没有相同的，而来了一个 $p$ 就出现了 $q$ 是相同的，所以前面一定有一个 $q$，$a_p$ 也肯定是 $q$。
我们先这样做，假设初始 $S=\{1\}$，每次按照 $p=2,3, \dots, 2n$ 的顺序，插入 $S$ 并查询，如果遇到非 $9$ 值，那么就赋值并在 $S$ 中删除 $p$，以保证 $S$ 的性质。
经过 $2n-1$ 次询问后，我们成功得到了 $n$ 个 $a_i$ 的值。现在，我们令 $S’=\{p:a_p 已确认\}$，然后对于每一个没有确认的 $a_i$ 查询 $S\cup \{i\}$，因为 $|S’|=n$，而 $S’$ 也满足 $S$ 的性质，所以查询结果一定不是 $0$，所以我们直接令 $a_i=q$ 即可。于是这就花掉了 $n$ 次查询。
最终，我们仅用了，且稳定用了 $3n-1$ 次查询就得到了 $a_1, \cdots, a_{2n}$ ！
Practice Submission
2160E Rectangles
这题事实上挺唐的。属于是一眼题了，洛谷也许给不到蓝。。。
我们考虑使用 $O(n^3)$ 量级的解法，先枚举左右端点 $[l,r] \subset [1,n] \; (l \ne r)$，然后枚举 $j \in [1,m]$，得到 $\{j:G_{l,j}=G_{r,j}=1\}$，用这些矩形的面积 对所有在相应矩形内的点更新即可。此时仍然是 $\mathcal O(n^2m^2)$，我当时使用线段树优化，$\mathcal O(nm\min\{n,m\}\log_2\max\{n,m\})$ 还是过不掉。
优化呢，“用脚都能想到”。（¿）
注意到，我们枚举 $r$ 的时候，$l$ 不变。所以从 $l$ 到 $n$ 这些区间我们可以取一个最小，也就是等 $r$ 做完之后再取后缀最小。然后每次枚举 $l$ 更新一次最终的答案矩阵。这样时间复杂度就是严格的 $O(n^3)$ 量级。
但是这题还是有点烦的，因为你要对于 $n \le m$ 和 $n > m$ 分开做，或者干脆输入输出的时候翻转一下。这个细节也不能忘了。
Practice Submission