CDQ 分治入门题

· · 题解

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'<x\land y'>y\land t'<t]

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

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

Part3 常数

我居然被卡空间常数了！

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

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

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