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

· · 题解

太菜了没做出来。

本题解期望给出本题的一个思考过程。

令 \ge x 的数为 1，<x 的数为 -1，设 s_i 是前缀和，则好区间等价于 r-l\ge k 且 s_r\ge s_l。

试着对上面的性质考虑算法，但我没考虑出来。

正推不会就倒推一下。由于最终好区间互不包含，它们的左端点和右端点分别是单调的。区间计数这类区间可以用差分的方式。具体地，对于询问 [L,R]，考虑所有好区间数量减去 r>R 和 l<L 的好区间数量。

所以实际上需要研究的是端点在 x 下是否作为好区间的端点。

以右端点为例，初步的想法是维护 x 下所有好区间的右端点。但发现 check 一个右端点是否合法仍旧很困难，原因在于可能产生新的包含关系。对于时刻变动的序列求解包含关系是困难的。

所以想办法让它不变。一个 trick：将时间扫描线维护下标数据结构变为下标扫描线维护时间数据结构。

一个时刻要维护什么才能刻画包含关系？显然只需要考虑上一个右端点。考虑上一个端点是 j，这个端点是 i，分析何时 i 不被 j 支配。接下来记 l_i 表示 i 对应的左端点。

对 s_i-s_j 分讨。当 s_i>s_j 时，由于变化量为 1，l_j+1 必然合法；反之，则任意对 i 的顺序对也必然是对 j 的顺序对，需要合法必然使长度不合法，即 j-k<l_i\le i-k，只要这段范围内有顺序对 i 就是合法的。

然而这并不能帮我们找出 i 所有的合法 x，但是与刚才不同，手模这个会发现合法的 x 似乎是一个前缀。考虑如果一个 x 合法，对于 x-1，相当于一个后缀加，这不会影响顺序对的相关性质。具体证明还是需要分讨，这里不多赘述。

到此性质已经分析完了。关于上面的维护，说明 s_i\le s_j 的情况，相当于让我们求一个历史最小值。对于 \le j-k 的部分，发现这恰好就是 j 合法的范围，可以在执行 j 的操作时将这一部分的历史最小值清空来实现。

维护历史最值那部分是经典地。如果你不会可以考虑先列个矩阵，再打表获取矩阵有效位、等价位，最后手动模拟即可。

代码私信给。