WC2023云游记

· · 个人记录

T1

把边界对应成 1,-1，冷静一下发现是找一对距离为 q 的数，分别为 1,-1。

这是一个经典的二分问题，用线段树支持 O(\log m) 查询单个位置即可。

具体地，因为支持离线，把所有位置记录下来离散化就可以使得常数比较小。

T2

写一下思维过程。

首先考虑一个个放，那么发现除非是最后一个，能放当且仅当剩下的人不都属于同一个集合。

此时注意到如果有一个集合特别大，具体地，有 2/3n 这样大，那就无解，因为一定有这个集合中的三个数相邻。猜测这就是充分必要条件。

然后给出构造。为了避免繁琐的讨论，我们发现有一个集合恰好是 2/3n 的时候是容易构造的，只用两个隔一个即可。那么我们就可以一个个往后写，直到有一个集合大小恰好为 2/3n。注意这里的细节：如果最大一种有 2k+1 个，剩下的有 k+1 个，那么我们之后两个各填写一个即可。在恰好 2/3n 之后剩下的两个隔一个即可， 就可以做到除了接起来的位置都没问题。现在如果愿意讨论怎么接起来也可以讨论，当然一种更好的写法是分析出直接打乱多来几遍有 \Theta(1) 的正确率，随机即可。

T3

O(n^2)：

把边从小到大换上去，或者任何你喜欢的算法。

O(n \log n)

我们先随机打乱边，然后询问出所有点的答案。之后我们将维护所有点的答案，并且将边变为一个类似小根堆的结构。假设现在 1,2,\cdots,k 均和根连通并且满足小根堆性质，我们要把 k+1 换到合适的位置。当然如果有点答案为 k+1 那么可以认为 k+1 已经在合适的位置了；反之我们设当前大于 k 的最小答案为 l，将 k+1 和 l 交换。此时答案改变的点只可能是刚才答案为 l 的点，暴力再更新一遍即可。

看起来很暴力，但是复杂度是对的。这是因为每个点被更新的次数是到根路径上边权的后缀最大值个数。

得到小根堆之后，我们注意到将 1,2,\cdots,n/2 依次换为 n/2+1,\cdots,n 然后询问权值就能知道这些点的父亲。这一部分确定之后我们可以再询问剩余点的权值知道他们的父亲；此时再换回去就规约到了一个规模为原来一半的问题。这一部分是线性的，需要约 T(n)=T(n/2)+n=2n 次两种操作。

上面的看起来轻飘飘实际上写起来有很多细节。比如 n/2 具体应该 +1 还是 -1。由于我们的目的是合理的询问便能一次确定想要的权值，我们需要把 i 和 i+\lceil n/2\rceil 交换，其中 1 \le i \le \lfloor n/2 \rfloor。

这样已经能过很多点了。这里的 \log n 其实是 \log \text{dep}，并且底数可以认为是 e。加上最后一档 B 部分分不用开头的随机打乱，有可能能卡过去，具体不清楚。

update：经测试，可以通过需要的部分分。调了 3h，有待提高/px code

O(n \log \log n) 链

上面那个算法还有压榨的空间！因为他带一个 \log，我们希望对 O(n/\log n) 个点先做一下。

一个想法是做好之后，把他们随机撒到树上，就能把树分成 O(\log n) 的块，但是可能不满足序关系，导致前功尽弃。

所以，我们不如直接排序。拿出最大的 O(n/\log n) 个边，将他们排序。

排序的方法是，我们要先再找 M=O(n/\log n) 个点来做参考。我们在这一步中将不再询问这些点以外的点的权值。把 n-1 放到一个随机位置，然后看这些点有多少个在他下方。最好随到一个比较均匀的位置，不过也只要 O(1) 步。然后把 n-1 和 n-M 交换，再通过随机交换把 n-1,\cdots,n-M 都放到这条边下面。有没有成功可以检查这个点的值来判断。现在再用一样的道理把前面一半点放到它上面，就完成了一次分治。递归下去即可，我们这里的复杂度是 T(M)=O(M)+2T(M/2)=O(n)。

排完序之后，我们就成功的把链分成了期望 O(\log n) 的块。此时再使用上面的算法。我们再暴力更新的时候，无须向块外的点进行任何更新，因为在处理新块时，我们可以直接重新询问所有块内点，这样每个点的更新次数就变为了块内后缀最大值个数，也就是 O(\log \log n)。

比较遗憾的是，虽然瓶颈 O(n \log \log n) 中常数为 1，但是排序部分常数比较大，外加它可能不太稳定，递归到最后 O(1) 层可能出现位置不够的情况，感觉这个算法很难在 7n 次操作内稳定出结果。由于出题人并没有在任何地方放宽这个常数，他大概没法比上面那个做法多多少分。我暂时并没有实现这个做法，希望之后有空可以补上代码。

线性做法

不会！

后记

这题可以算是我做过最好的交互题了，大概也是最难的。虽然我现在还不会。orz 出题人！