P4747 [CERC2017] Intrinsic Interval
2026-09-10
题解
题目中的区间 [l,r] 判定可以等价为:max−min=r−l。
由于给定区间,求最短包含合法区间,考虑把询问离线下来,枚举 r。
稍微移个项,我们在线段树上维护 f(l,r)=max−min−r+l。
其中 −r+l 的项可以通过每次移动右端点时对整个线段树 −1,初始建树时把叶子 l 的值设为 l。
移动右端点时,区间 [l,r−1] 变为 [l,r],我们对整个线段树 −1,但新加入的元素 a[r] 可能对 max,min 有影响,我们以最大值为例。
当新元素 a[r] 取代了原栈顶元素 y,那么影响的左端点范围为上一个栈顶 +1 到 y,对这段区间 −a[y],然后将 y+1 到 r 加上 a[r] 即可。
对于查询,将询问 [x,y] 离线到 y 上,然后枚举右端点。
维护一个 multiset,内部按照左端点逆序排序,然后找到左端点最大的询问 [x,y],此时在线段树上查询 [1,x] 中最大的、值为 0 的位置 l,此时答案即为 [l,r],然后继续找下一个最大的询问。
注意,在这期间如果 [1,x] 中不存在的话直接枚举下一个 r,因为最大的 x 都找不到 [1,x] 的 0,更小的也不会有。
