题解：P13780 「o.OI R2」愿天堂没有分块

Eric998 · 2025-09-26 22:44:05 · 题解

好题。我还是见的太少了。想了 1h+ /ll

看到奇奇怪怪的点对问题，首先考虑支配对。

支配对看起来很难找。只找 \operatorname{mex}>1 的。先写一个形式化的定义。因为区间变小 \operatorname{mex} 不升，所以 [l,r] 是支配对，当且仅当其 \operatorname{mex}>1，且 \operatorname{mex}(l,r-1)\neq \operatorname{mex}(l,r),\operatorname{mex}(l+1,r)\neq (l,r)。

处理 \operatorname{mex} 比较优秀的工具是扫描线时维护每个数上一次出现的位置 las_i。扫描支配对的右端点 r，维护 las_i。

若存在一个 \operatorname{mex}=p 的右端点为 r 的区间，则满足扫描到 r，在 p 的最后一次出现前，[1,p) 都出现了。观察到这就等价于 las_p 是 las 的一个前缀最小值，此时 \displaystyle[\min_{i\in[1,p)}las_i,r] 是一个 \operatorname{mex}=p 的区间。注意到此时左端点是极右的。

已经保证左端点极右，要得到支配对，只需保证这个点对的右端点极左。

我们需要线段树动态维护 las 的前缀最小值。考察我们修改 las 只会使其增加；因此若修改的位置目前不是前缀最小值，则没有影响。若目前的位置是前缀最小值，则从该位置之前的前缀最小值向右不断做线段树二分找到前缀最小值，每次把二分到的位置作为一个支配对存下来，直到找到之前就是前缀最小值的位置。这样，每个 \operatorname{mex}=p 的区间只在其第一次出现（即右端点极左）被记录。

因为修改单调增，所以之前的前缀最小值（除了被修改的）一定还是前缀最小值。

考虑此过程的复杂度证明。las 一共只会被修改 n 次；每个值都最多会在被加入和移除前缀最小值时产生 O(\log n) 的复杂度。所以找支配对是 O(n\log n) 的。

剩下的部分就是 *800 了。把支配对和询问再拿下来挂在右端点上，扫描线，维护一个新的 las 即可。具体参照离线区间 \operatorname{mex}。