题解：P14463 【MX-S10-T4】『FeOI-4』呼吸之野

令 $[1,m]$ 为值域。

枚举 $mid=1\sim m$，将 $<mid$ 的位置设为 $-1$，$\ge mid$ 的位置设为 $1$。每次将一个位置 $1\to -1$。对于每个位置 $i$，维护 $f_i$ 表示使得区间 $[j,i]$ 合法的最大的 $j$。

考虑如果存在 $i<j,f_i\ge f_j$，那么区间 $[f_j,j]$ 就包含了区间 $[f_i,i]$。所以在当前时刻，区间 $[f_j,j]$ 就没有用了。并且当 $mid$ 继续变大时，$[f_j,j]$ 还是会包含 $[f_i,i]$。所以可以直接将位置 $j$ 删掉。

于是我们发现一个右端点会在一个前缀时间存在。那我们考虑扫原序列，维护 $mid=1\sim m$ 的信息。

考虑对于一个 $mid$ 我们如何处理。首先我们需要维护上一个有用的位置。

令当前位置为 $i$，上一个有用位置为 $j$。考虑如果 $a[j+1,i]>0$，显然 $f_j<f_i$。所以我们考虑什么时候 $a[j+1,i]\le 0,f_j<f_i$。 注意到若 $a[f_i,i]\ge 0$，那么 $a[f_i,j]\ge 0$。也就是说，若点 $f_i$ 对于 $j$ 不合法，那么 $j-f_i+1<k$，即 $j-k+1<f_i\le i-k+1$。我们发现这个区间的长度 $=[j+1,i]$。那么我们就可以用一个线段树维护前缀和 $a[1,i-k]$ 和历史最值。然后当位置 $i$ 变成新的有用的点时清空历史最值。用线段树维护每个 $mid$ 的信息，使用线段树上二分求出最后一个存在时间，可以做到 $O(n\log n)$。

考虑将查询按照 $x$ 从小到大处理，维护所有没有被删掉的点。然后答案会是一段区间，直接二分求出来即可。时间复杂度 $O(q\log^2 n)$。

考虑用上述做法倒着做一遍，可以得到有用的左端点集合，并且两个集合的点是一一对应的。那么可以直接找到区间。时间复杂度 $O((n+q)\log n)$。