本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 的数量。

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