自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:45:05，当前版本为作者最后更新于2023-02-12 14:48:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part1 前言

Ynoi 开始普及三维偏序？结果被我这个场外拿了一血？

只要你会 CDQ 分治就一定能场切这道题，因为它实在是太模板了，要是强制在线的话还要写带插入 K-D Tree 就要麻烦一些。

Part2 解法

为什么没有思考过程和错解？因为这是一道模板题。

题意是单点改全体本质不同逆序对，如果不要求本质不同就没有任何技巧了。

但是他要我本质不同，我就要想办法把本质不同去掉。

去掉的方法也很容易想到，设 $fst_x$ 表示 $x$ 第一次出现，$end_x$ 表示 $x$ 最后一次出现，那么一个逆序对等价类 $(a,b),a>b$ 就可以用 $fst_a,end_b$ 来表示。

发现每一次修改变化的 $fst_x$ 和 $end_x$ 数量是 $O(1)$ 的，可以用 std::set 维护每一种数字出现的位置，这样就能将每一次修改的贡献转化为三维偏序。

例如，一个三元组 $(x,y,t,0)$ 表示在 $t$ 时刻，$fst_x$ 变为了 $y$，$(x,y,t,1)$ 表示 $end_x$ 变为了 $y$，那么贡献就分别是：

1. $w(x,y,t,0)=\sum\limits_{(x',y',t',1)}[x'>x\land y'<y\land t'<t]$
2. $w(x,y,t,1)=\sum\limits_{(x',y',t',0)}[x'y\land t'<t]$

当然会有撤销的情况，再加一维表示加还是减就可以了。

时间复杂度 $O((n+m)\log^2(n+m))$，空间 $O(n+m)$，可以轻松通过。

Part3 常数

我居然被卡空间常数了！

这道题的结构体是个五元组，且要开十倍，并且因为需要归并所以要再开一个！

不过如果不使用归并，每次暴力 sort，那样空间直接减小一倍，只是稍微慢一点，不影响复杂度。

当然，时间并不卡常，毕竟是 CDQ 分治。