Replace

cplusoj 链接

题意

给你一个长度为 \(n\) 的序列 \(A\)，有 \(q\) 次询问，每次询问对于一个区间 \([l,r]\) 需要操作多少次才能变成区间 \([1,n]\)，无解输出 \(-1\)。其中一次操作指原区间变成 \([l'=\min_{i=l}^r\{a_i\},r'=\max_{i=l}^r\{a_i\}]\)。

solution

看了feecle大佬的题解后对其中的结论有也许是另一种理解方式。

首先题目的操作与取 \(\min,\max\) 有关，因此通过丰富的经验和敏锐的观察力显然我没有可以发现：

证明（或者应该叫理解方式）：对于每个 \(i\)，设 \(a_x=\min(a_i,a_{i+1}),a_y=\max(a_i,a_{i+1})\)，\(f(i,i+1)\) 对应区间 \([a_x,a_y]\)，其中相邻的 \(i\) 对应区间至少有一个端点重合。因此所有的 \(f(i,i+1)\) 并成连续的一段区间，其中最左的一个端点和最右的一个端点就是 \(f(l,r)\) 的两端。可见等式是成立的。

蒟蒻的我不能直接观察出推论，但是也许可以这么想：我们考虑对所有 \(f(i,i+1)\) 再进行一次操作，看看会发生什么。\(f(i,i+1)\) 是若干段首尾相接的区间。每个区间会变成区间最小值和最大值为端点的新区间。由于区间是首尾相接的，因此新区间要么首尾相接要么相交得更多，而所有新区间的最左端点和最右端点一定等于所有区间的最小值和最大值，因此对这些 \(f(i,i+1)\) 再进行一次操作，得到的区间 \(=f^2(l,r)\)。

以此类推，可以得到 \(f^k(l,r)=\cup_{i=l}^{r-1} f^k(i,i+1)\)。

所以我们不需要求所有的 \(f(l,r)\)，只需要求所有的 \(f^k(i,i+1)\)。然后是 RMQ 问题求区间最小值和最大值，ST 表即可。

因为 \(f(1,n)=[1,n]\)，所以显然操作 \(k\) 次能否得到区间 \([1,n]\) 的 \(k\) 满足单调性，\(k\) 越大越容易得到指定区间。

因此考虑倍增。先求所有 \(f^{2^0}(i,i+1)\)，然后求所有 \(f^{2^1}(i,i+1)\)，以此类推，每一层都要做一次 RMQ。时间和空间都是 \(O(n \log^2 n)\)。

对每个询问，倍增，每次计算 RMQ 判断是否可以得到区间 \([1,n]\) 即可。时间复杂度 \(O(q \log n)\)。

总时间复杂度是 \(O(n \log^2 n+q \log n)\)。

据说猫树可以单 \(\log\)？感觉不会啊，会的大佬欢迎分享。