P3157 [CQOI2011] 动态逆序对 分析

__ryp__ · 2024-02-13 21:39:07 · 个人记录

首先离线，将时间抽为第三维，然后我们考虑每一次的删除会导致逆序对减少多少。

我们设每个点的第一维 x_i 为它被删除的时间（或正无穷），第二维 y_i 是它的下标，第三位 z_i 是值，那么一个点 p 被删除后，逆序对减少的数量，就是使得 x_p \le x_q, \space y_p \lt y_q, \space z_p \gt z_q 或者 x_p \le x_q, \space y_p \gt y_q, \space z_p \lt z_q 的 q 的数量。

于是我们的问题就变成了三维偏序：先算出初始的逆序对数量（这时候是个二维偏序），然后统计在每一个时间上上面两个偏序的总数量，相减即可。