题解：P6829 [IOI 2020] 植物比较

· · 题解

小清新题，有很好的教育意义。

其实这个问题交给你，明显是让你找到合理利用他给你的信息的方式。

解决这题最合适的方式，就是我们通过考察极值去利用信息。我们考虑最大值满足的条件是什么，首先要求 r_i=0，且要求 \forall 1\le j<k,r_{i-j}>0。

我们发现，对于所有满足条件的 i，我们可以证明它是 [i-k+1,i+k-1] 中的局部最大值。

进一步的，我们找到这样的 i，并将 i 加入排列，然后删去它，影响是将 [i-k+1,i-1] 位置的 r 减一。然后进一步找接下来的局部最大值。如果两个位置的距离 <k，那么我们可以根据它们的排列中的前后关系判断其大小。

我们可以将能够判断大小关系的元素之间进行连边，大的连向小的。那么询问相当于是问能否找到一条 x 到 y 或者 y 到 x 的路径，有就可以判断大小，没有就无法判断。

你发现我们通过刚刚的方式建出来的图信息量是足够充分的，显然你无法获得更多的信息。

现在考虑怎么加速过程。

首先加速排列的维护过程。对于 r_i=0 的位置在动态修改的环境下我们可以线段树维护，维护区间最小值及其位置。然后还有一个性质叫做前 k-1 个 r_i>0，由于该限制是一段区间，那么我们再利用一棵线段树，初始每个位置的权值为 n（足够大的值），当加入 r_i=0 的 i 就给 [i+1,i+k-1] 区间加 1，并给 i 减去 n。然后仍然维护权值最小的元素即其位置。

我们从 1 扫到 n，对于第 j 轮我们先加入所有 r_i=0 的 i，然后从第二棵线段树里找到合法的位置加入排列并处理其删除后的影响即可。

对于后面的找路径我们需要多分析一些性质。我们发现我们连边的限制仍然是一对区间，于是我们把视角放在环上就可以意识到我们一条路径完全没必要折返，直接往同一个方向走即可。而我们关心的，是一直往同一个方向走最远能走到哪。我们可以考虑往某个方向的最小的大于它的位置走一定不劣，这个东西直接倍增维护即可。