题解：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)。