题解：P13075 [NOISG 2019] Pilot

· · 题解

发现原题等价于给一个区间，将 \forall i,b_i\le Y_i 的值全部赋值为 1 否则为 0，求全由 1 构成的区间个数。

容易发现一个符合条件长度为 b_i 的极长子区间对答案贡献 f_i 为：

f_i=b_i\cdot(b_i+1)

可以直接将询问离线下来数组 Y 和数组 b 排序，然后按顺序将满足 b_i\le Y_j 所在 i 赋值为 1，然后累加答案。

具体实现，可以在每次加入时检查该点左右两个相邻的点是否也已经被赋值为 1，如果是则合并这两个区间。计算答案时，可以先分别减去两个区间的答案，再加上新区间的答案。