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

· · 题解

考虑求出了所有区间后如何统计不被支配的区间数量。每个右端点只可能贡献最靠右的左端点，记这个左端点为 f_i，则答案为 f_i 的前缀最大值数量。

将 \geq x 的位置设为 1，<x 的位置设为 -1 之后，[l,r] 合法当且仅当区间和非负。注意到 i 作为右端点时，不被支配的 x 会是值域的一段前缀。证明考虑随着 x 的增大，f_i 只会往左移，讨论一下区间正负。

于是需要求出每个 i 不被支配的前缀。对于一个 x，只需要关心此时 <i 最后一个不被支配的右端点 j，判断 j 是否支配 i。当 \sum\limits_{j+1}^ia>0 时，f_j+1 对于 i 合法，此时必然不会被支配。否则 \sum\limits_{j+1}^ia\leq0，有 \sum\limits_{f_i}^ja+\sum\limits_{j+1}^ia\geq0，后者 \leq0，因此前者 \geq0，于是在不考虑 k 的限制下，f_i 对 j 合法。所以当 \sum\limits_{j+1}^ia\leq0 时，i 不被 j 支配意味着 (j-k+1,i-k+1] 中存在一个对于 i 合法的左端点。

扫描序列维，线段树维护时间维，\sum\limits_{j+1}^ia>0 的情况可以直接线段树维护区间最大值，线段树二分找到最后一个合法的 x。\sum\limits_{j+1}^ia\leq0 时，记录前缀和 s_i，线段树上维护 s_i-\min\limits_{j-k+1}^{i-k}s，这个可以通过维护 s_i-s_{i-k} 以及历史最大值来做到，同样线段树二分找到最后一个 \geq0 的点。设 i 覆盖的前缀是 [1,x]，则清空 1\sim x 的历史最大值，剩下的操作可以用 O(1) 次区间加来刻画。

考虑查询 [ql,qr],x。考虑区间内所有 x 时没被支配的 i（这在求出所有 i 不被支配的前缀后是好维护的），能产生贡献的会是这里面的一段后缀，二分一下，需要求 x 时 f_i 的值。这可以数据结构简单维护，时间复杂度 2\log。

实际上用同样的做法可以维护每个左端点不被支配的前缀，考虑 x 时左右端点一一对应，直接利用区间内最靠左的合法左端点来数据结构上二分出其对应的右端点即可，时间复杂度 O(n\log n)。