[AH2017/HNOI2017] 影魔

_32_qwq · 2024-11-21 11:54:59 · 题解

考虑扫描线。

首先我们扫描线的时候应该想：我们 DS 上需要维护的是什么？

对于本题，有一个非常暴力的做法就是直接在 DS 上维护每个点 p 在扫到 r 的时候 [p,p+1],[p,p+2],\cdots,[p,r] 的贡献的和。

从这个思路出发，我们就只用考虑每一个 [l,r] 的情况了。

直接算贡献不好算，我们可以考虑给它转化成式子的形式。

贪心地，我们显然是要看区间里面又没有 >k_i 和 >k_j 的数，因此我们只需要找第一个位置即可。因此令 L_i 表示 i 左边第一个比它大的位置，R_i 表示 i 右边第一个比它大的位置。那么贡献为 p_1 就等价于 R_l\ge r,L_r\le l ，然后贡献为 p_2 的时候，就只有其中一个成立。

显然 R_l<r 和 R_l\ge r 的式子并不一样，所以我们需要开两个 DS 来分别维护，然后在 R_l=r 的时候，把它从第一个 DS 放到第二个 DS 里面。

最后再来考虑一下用什么 DS 来维护。

首先我们需要进行快速的插入和删除，然后我们需要对 L_r\le l 和 L_r>l 分开处理，并且只操作在这个 DS 里面的，而不是批量的区间操作。查询也只查询 l\ge a_i 的部分并且要在这个 DS 里面，而不是区间查询。

容易发现，上述操作可以用 FHQ Treap 维护，时间复杂度 O(n\log n)。（是否可以用线段树维护未知）