[三维偏序] P3157 动态逆序对

_Cheems · 2024-01-29 07:27:04 · 个人记录

考虑删去一个点的影响。

考虑该点的逆序对数量。

考虑去重（晚删的显然不能再和早删的组成逆序对计入答案）。

考虑加上时间维 tim，那么对于 i，一对逆序对能它被计入当且仅当：i<j,a_i>a_j,tim_i<tim_j。

或：j<i,a_j>a_i,tim_i<tim_j。

构成三维偏序，解决。