[EGOI 2023] Guessing Game

精彩。

这篇题解有思路讲解，只想看做法的可以看其它题解。

做题第一步一定是先把题目要干什么弄清楚。不妨令这题第一个人是 A（除了最后一个访问的元素的信息填写者），第二个人是 B（接收信息者），第三个人是 C（最后一个访问的元素的信息填写者）。

A 可以为每个出现在最后一次访问之前的元素填颜色，设第 \(i\) 个访问的元素编号是 \(p_i\)，那么 A 可以知道 \([1,i]\) 中第 \(j\) 个访问的编号，或者说关于前面的所有信息。

B 可以知道颜色为 \(c\) 的所有元素的编号。

最后一次访问的元素颜色可以由 C 乱填。

现在要构造一种策略使得能够让 B 找出最后一个访问的元素，并最小化颜色数量。

考虑一个最简单的构造。A 直接填每个元素是第几个访问的，B 直接回答颜色重复的两个元素即可，这样可以拿下 \(10\) 分。

我们发现我们并没有利用编号带来的信息。考虑利用编号进行一些区分。我们按编号奇偶性分成 \(2\) 个集合，A 的策略是每个元素填它在自己所在集合中是第几个被访问的，B 在处理信息时如果最后存在一个颜色有 \(3\) 个元素，那么回答这里面奇偶性相同的两个数即可。如果不存在就直接回答颜色为 \(\frac n 2\) 的两个元素即可，因为此时 C 一定也是按规则填的，于是我们做到了 \(K=\frac n 2+\mathcal{O}(1)\)。

看看能否更近一步？我们按 \(\bmod B\) 的结果进行分类，然后跑类似的过程，但是会出一个问题，就是如果 C 按规则填，那么我们需要回答 \(B\) 个数，毁了。考虑能不能修，我们发现如果填一个元素时它已经是同种元素的最后一个，那么我们计算有多少个集合已经在前面全部访问过，然后颜色加上这个数字即可，最后分讨一下即可。此时可以做到 \(K=2\sqrt n+\mathcal{O}(1)\)。

但是这这个做法似乎无法拓展了，我们这种做法对编号的利用存在局限性，不够充分，想想有没有办法更充分的利用编号信息。

刚刚我们的做法其实是利用了编号的数论性质，我们自然考虑继续利用数论性质，但是分析起来会发现很难更进一步，所以我们可以考虑跳出数论性质的思想，思考一些其它的做法。

信息很多很乱，\(K=7\) 太抽象，先一步一步来，看能否将 \(K\) 控制在 \(\log\)。考虑利用一些我们熟悉的简单结构刻画利用信息。关于 \(\log\) 你能想到什么？二分似乎看起来不太能做，启发式合并更为抽象，分治倒是可以考虑，但是我们现在的思想是利用编号带来更多信息量，所以我们不妨考虑比分治更厉害的线段树，我们按编号为下标建立一棵线段树，按访问顺序加点，我们希望用颜色刻画整个过程，可以考虑一种激活思想，当线段树结点代表的区间 \([l,r]\) 全部访问过，则线段树结点被激活。不难发现每次加点时激活的结点一定是一个从当前代表 \(p_i\) 的结点开始到它的一个最浅的祖先，我们直接将 \(p_i\) 的颜色刻画为到达最浅的祖先的深度。

而最后访问的点可以胡乱激活，不讲道理。

这样刻画之后，我们颜色结合编号后，编号可以带来很多对访问顺序的限制，我们要利用这些限制与性质试着找出最后访问的结点，考虑有哪些性质可以被利用：

1. 每个线段树结点只能被一个结点激活。
2. 最后访问的元素结点到祖先的所有线段树结点都无法在访问其它元素时激活。

理一下思路，最后访问的点理应激活到根，但如果没有激活到根，则一定会出现一个问题，即存在一个结点没有被激活，但是其左右儿子都被激活了！其中一个儿子必然包含是最后访问的元素激活的。于是我们可以直接记录每个结点 \(u\) 是在访问到谁的时候被激活的，设其为 \(id_u\)，然后找到刚刚不合法情况的左右儿子，回答它们的 \(id\) 即可。

于是我们做到了 \(K=\log n+\mathcal{O}(1)\)。

这个时候貌似我们对编号信息的利用已经到极限了，考虑这个做法有没有继续走下去的机会。

你发现我们的线段树一定可以找到最后一个访问的是谁，那么我们可否尝试缩小线段树的规模？相当于是说我们大部分元素的信息其实我们可以并不关心，我们只需要利用少部分信息，\(K\) 自然也会变少。

由于后缀获得的信息严格强于前缀，我们不妨只关心后 \(2^k\) 个访问的元素的信息，我们对这些点建线段树，对于前面的我们令其颜色为 \(k+1\)，这样如果 C 给最后一个填 \(k+1\) 问题会比较棘手，考虑这种情况怎么处理。

此时对于 B 我们知道在 \([n-2^k+1,n-1]\) 访问的元素集合，那么对于 A 我们能做什么？A 可以知道 \([n-2^k+1,n]\) 访问的元素集合，现在我们希望通过一些信息传递找到第 \(n\) 个元素。这里就可以利用运算构造的思想，我们考虑一种具有可减性或可消除性的运算方式，这里我们可以考虑加和或者异或，我用异或进行讲解，异或即求元素编号的异或和。

那么我们现在就有一个思路，A 使用一种刻画信息的方式刻画出它们的异或值，B 解码得到值再异或 \([n-2^k+1,n-1]\) 的所有元素编号就能解出最后一个元素的编号，具体怎么办呢？

首先我们要想利用颜色表示一个数不难想到把每个数位展示出来，考虑利用二进制，因为二进制只有 \(0\) 和 \(1\)。我们正常来讲需要记录 \(17\) 位，但是由于 B 可以回答两个数，我们可以不妨把最后一位的信息删去，这样就只需要 \(16\) 位了。

很明显，A 在回答完第 \(n-2^k\) 访问的数时才能知道它们的异或和，所以我们也只能在这之后传递数的信息。显然我们只能赋予一种颜色两种意义，在线段树中它有一个意义，而在数位中它有另一个意义。

不妨把颜色为 \(k\) 的所有数找出来，这样的数一共会有 \(2^{k-1}\) 个。此时我们把前缀填的颜色改为 \(k+2\)，然后利用 \(2^{k-1}\) 个数表示我们要的二进制数，如果数位为 \(0\) 就填 \(k\)，否则填 \(k+1\)。

此时令 \(k=5\)，则 \(K=k+2=7\)，做完了。

还有一些实现细节。很明显我们可以在处理完第 \(n-32\) 访问的元素后对最后 \(32\) 个数进行编号大小的排序，也就是离散化，这样就可以完全将线段树规模控制住。然后表示二进制数显然需要确定一个表示顺序，不妨也按编号大小排序。要想确定一个颜色为 \(k\) 的具体表示的位置是简单的，因为我们发现相邻两个位置有且仅有一个颜色为 \(k\)，所以它表示的位置一定是它排好序后的位置 \(\lfloor\frac {pos-1} {2}\rfloor\)。

这题利用了很多思想，利用我们会的结构或思想，减少设计信息规模，再平衡规模和利用可消除性运算解决问题。并且要求我们面对复杂问题在各种思想和 trick 中来去自如，这就是熟能生巧的东西了。