逆序对问题的总结
yangzichen1203
·
·
算法·理论
省流：
- 静态全局逆序对：O(n\log n)。
- 单点修改全局逆序对：O(n\log^2n)。
- 区间覆盖全局逆序对：O(n\log^2n)。
- 区间逆序对：O(n\sqrt n)。
- 单点修改区间逆序对：O(n\sqrt n)。
- 区间覆盖区间逆序对：O(n\sqrt n)。
- 区间本质不同逆序对：O(n\sqrt n)。
- 二维支配对：O(n\sqrt n)。
- 三维/更高维支配对：？？？
- 区间翻转全局逆序对：O(mn^{\frac{2}{3}}\log^{\frac{1}{3}}n)。
- 区间排序全局逆序对：O((n+m)\log n)。
- 区间排序前缀逆序对：O((n+m)\log n)。
1 静态全局逆序对
题目
P1908
做法
树状数组或归并排序。
时间复杂度：O(n\log n)
空间复杂度：O(n)
2 单点修改全局逆序对
题目
P3157
在线
树状数组套权值线段树。
时间复杂度：O(n\log^2n)
空间复杂度：O(n\log^2n)
离线
cdq 分治。
时间复杂度：O(n\log^2n)
空间复杂度：O(n)
3 区间覆盖全局逆序对
题目
无
在线
颜色段均摊，树状数组套权值线段树维护颜色段。
时间复杂度：O(n\log^2n)
空间复杂度：O(n\log^2n)
离线
暂时不会非常优秀的做法。
4 区间逆序对
题目
区间逆序对
在线
P5046
分块。
如果左右端点不在同一块内：
整块对整块：全部预处理出来 f_{l,r}，时间复杂度 O(n\sqrt n)，空间复杂度 O(n)。询问直接查表，时间复杂度 O(1)。
整块对散块：预处理前 i 块小于等与 j 的数的数量 cnt_{i,j}，时间复杂度 O(n\sqrt n)，空间复杂度 O(n\sqrt n)。询问直接查表，时间复杂度 O(\sqrt n)。
散块对散块：维护排序后块内的值 b，时间复杂度 O(n\log n)，空间复杂度 O(n)。询问归并排序计算 f(l_1,r_1,l_2,r_2)，时间复杂度 O(\sqrt n)。
整块内：树状数组预处理贡献 val，时间复杂度 O(n\log n)，空间复杂度 O(\sqrt n)。询问直接查表，时间复杂度 O(\sqrt n)。
散块内：预处理每个块的前缀和后缀的贡献 pre,suf，时间复杂度 O(n\log n)，空间复杂度 O(n)，询问直接查表，时间复杂度 O(1)。
如果左右端点在同一块内：
答案就是 pre_r-pre_{l-1}-f(L,l-1,l,r)。
时间复杂度：O(m\sqrt n)
空间复杂度：O(n\sqrt n)
离线
P5047
莫队二次离线。
时间复杂度：O(n\sqrt m)
空间复杂度：O(n)
5 单点修改区间逆序对
题目
https://www.luogu.com.cn/problem/T735337
在线
二维分块。
修改时考虑如何维护上面这些信息。
$cnt$：$O(n\sqrt n)$ 次单点询问 $O(n)$ 次矩形修改，用 $O(\sqrt n)-O(1)$ 的 $O(\sqrt n)\times O(n)$ 平面的二维分块维护。
$b$：块内冒泡排序，时间复杂度 $O(\sqrt n)$。
$val$：块内暴力计算贡献，时间复杂度 $O(\sqrt n)$。
$pre,suf$：块内递推处理，时间复杂度 $O(\sqrt n)$。
时间复杂度：$O(m\sqrt n)
空间复杂度：O(n\sqrt n)
离线
暂时不会非常优秀的做法。
6 区间覆盖区间逆序对
显然也满足颜色段均摊，同时发现做法 5 支持点带权，所以时间复杂度也是 O(m\sqrt n) 的。
7 区间本质不同逆序对
题目
P7448
在线
暂时不会做法。
离线
因为区间逆序对等价于区间排列逆序对，所以这题不弱于区间逆序对，时间复杂度至少为 O(n\sqrt{m})。
以下记 w([l,r],x) 表示区间 [l,r] 中小于 x 的数的个数，pre_i 表示值为 a_i 的上一个位置，nxt_i 表示值为 a_i 的下一个位置。考虑莫队二次离线，对于转移 [l,r]\to[l,r+1]，其贡献为
w([pre_{r+1}+1,r],a_{r+1})
=w([l,r],a_{r+1})-w([l,pre_{r+1}],a_{r+1})
=w([l,r],a_{r+1})-w([l,pre_{r+1}-1],a_{pre_{r+1}})
令 f(l,r) 表示 w([l,r],a_{r+1})，
=f(l,r)-f(l,pre_{r+1}-1)
我们发现 l 是不变的，所以我们把询问存成区间，挂到 vector 的 l 位置上，然后从右到左扫。可以维护一个二维平面，每次加入一个数时插入点 (i,a_i)，删除点 (nxt_i,a_{nxt_i}) 以保证无重复点，每次询问 (x,y)(x\le r,y>a_{r+1}) 的数的个数。
由于一共有 O(n) 次询问和 O(n\sqrt{m}) 次查询，所以我们需要一种 O(\sqrt{n})-O(1) 的二维分块来平衡复杂度。
分块方法：我们把 n\times n 的平面分解成大小为 n^{\frac{3}{4}}\times n^{\frac{3}{4}} 的 \textcolor{green}{0\ 类块}，大小为 n^{\frac{1}{2}}\times n^{\frac{3}{4}} 的 \textcolor{green}{1\ 类块}，大小为 n^{\frac{3}{4}}\times n^{\frac{1}{2}} 的 \textcolor{green}{2\ 类块}，大小为 n^{\frac{1}{2}}\times n^{\frac{1}{2}} 的 \textcolor{green}{3\ 类块}。
一个修改可以被分解成 O(\sqrt{n}) 个 \textcolor{green}{0\ 类块}，O(\sqrt{n}) 个 \textcolor{green}{1\ 类块}， O(\sqrt{n}) 个 \textcolor{green}{2\ 类块}， O(\sqrt{n}) 个 \textcolor{green}{3\ 类块}，和 \textcolor{purple}{4\ 散块}。显然最难做的是 \textcolor{purple}{4\ 散块}，但由于它的宽度只有 O(\sqrt{n})，且询问均满足 (x,a_{x+1}) 的形式，我们把 a 转成一个排列，所以最多只有 O(\sqrt{n}) 个可能的询问会用到 \textcolor{purple}{4\ 散块}。我们就枚举这些询问进行修改，时间复杂度为 O(\sqrt{n})。
查询就是所在块的标记之和加上询问的标记，由于只要查表，所以时间复杂度为 O(1)。
时间复杂度：O(n\sqrt{m})
空间复杂度：O(n)
8 二维支配对
题目：
P6579
P6774
在线
离线不逐块处理就是在线的了。
时间复杂度：O(n\sqrt n)
空间复杂度：O(n\sqrt n)
离线
这是对 OtomachiUna 题解的一点补充。
画图：
以下记每次询问为 x\in[x_0,x_1],y\in[y_0,y_1]。
Step 1：计算区域 1 对区域 1234 的贡献。这一部分可以先预处理出每一个点小于它的点的个数，再计算询问矩形内的点权和。两步都可以用二维数点实现，时间复杂度 O(n\log n)。
Step 2：计算区域 1 对区域 3 的贡献。这一部分就是区域 1 的点数乘上区域 3 的点数，同样用二维数点实现，时间复杂度 O(n\log n)。
Step 3：计算区域 1 对区域 4 的贡献。我们对 x 轴分块，对于每一个块，分开统计每一个询问在块内的贡献和块间的贡献。我们以下令块长为 O(B)，块的数量为 O(\frac{n}{B})，每个块的左端点为 L，右端点为 R。
Step 3.1：计算块内的贡献（点 a 对点 b）。我们预处理整块（x_0=L,x_1=R）的 y_0=l,y_1=r 的答案，对于一个点对 (i,p_i)<(j,p_j)，我们发现它当且仅当在 y_0\in[p_j+1,p_k],y_1\in[p_k,+\infty) 时有贡献。所以我们在 (p_j+1,p_k) 打上 +1 标记，在 (p_k+1,p_k) 打上 -1 标记，然后做一遍二维前缀和。时间复杂度 O(\frac{n}{B}\times(B^2+m))。然后我们暴力计算散块的答案，从左到右扫，维护一个 cnt，如果满足 p_i<y_0，cnt\to cnt+1，如果满足 y_0\le p_i\le y_1，ans\to ans+cnt。我们发现只有 O(m) 个这样的询问，所以时间复杂度是 O(mB) 的。
Step 3.2：计算块间的贡献（点 a 对点 c）。我们预处理每一个块中满足 x\le X,y\le Y 的点数，通过二维前缀和可以在 O(\frac{n}{B}\times B^2) 的时间复杂度内求出。对于每一个询问，从左到右扫，维护一个 cnt，扫到一个块时先将 ans\to ans+cnt\times sum_1，在将 cnt\to cnt+sum_2，其中 sum_1 表示满足 x\in[\max(L,x_0),\min(R,x_1)],y\in[y_0,y_1] 的点数，sum_2 表示满足 x\in[\max(L,x_0),\min(R,x_1)],y\in[1,y_0-1] 的点数，可以 O(1) 计算出来。时间复杂度为 O(\frac{n}{B}(B^2+m))。
Step 4：计算区域 1 对区域 2 的贡献。我们把 x 轴和 y 轴交换，再做一遍 Step 3 即可。
Step 5：总的答案就是 ans_{1234}-ans_2-ans_3-ans_4，总时间复杂度 O(n\log n)+O(n\log n)+O(\frac{n}{B}(B^2+m)+mB)+O(\frac{n}{B}(B^2+m))=O((n+m)B+\frac{nm}{B})，当 B=\sqrt{n} 时取到 O((n+m)\sqrt{n})。空间复杂度通过逐块处理，优化到 O(n+m+B^2)，当 B=\sqrt{n} 时取到 O(n+m)。
时间复杂度：O(n\sqrt n)
空间复杂度：O(n)
9 三维/更高维支配对
等价类分治？
10 区间翻转全局逆序对
题目：
P10028
离线
等价类分治。（想到了但不敢想）
对操作分块，设块长为 O(B)，则将序列分成 O(B) 个等价类。
对值域分块，设块长为 O(D)。
贡献：
- 同等价类。
- 不同等价类，同值域块。
- 不同等价类，不同值域块。
发现 1 容易统计，2 只有 O(nD) 个本质不同顺序对，3 相对困难。这里如果暴力做的话就会成
O\left(\dfrac{m}{B}\left(n\log n+nD+B^2\dfrac{n}{D}\log n\right)\right)=O(nm\sqrt{\log n})
不可接受。
考虑对修改范围等价类分治。设当前分治区间长为 O(k)，显然等价类数也是 O(k) 的。
需要记录的信息：
- 每个等价类的顺序对数。
- 每个等价类每个值域块个数。
- 相同值域块在每个等价类对间的个数。
分治过程：
- 继承上次等价类分治的序列，然后从下到上建树，记录每层等价类的翻转情况，并统计全局同值域块的顺序对，时间复杂度 O(B\log B+nD)。
- 向下合并值域块信息，时间复杂度 O\left(k\times\dfrac{n}{D}\right)。
- 向下合并等价类间相同值域块个数，时间复杂度 O(k^2)。
- 向下合并顺序对个数，每次再加上统计好的另两种信息即可，时间复杂度 O\left(k^2+k\times\dfrac{n}{D}\right)。
分治复杂度：
T(k)=2T\left(\dfrac{k}{2}\right)+O\left(k^2+k\times\dfrac{n}{D}\right)
T(B)=O\left(B^2+B\log B\times\dfrac{n}{D}\right)
时间复杂度：
O\left(\dfrac{m}{B}\left(nD+B^2+B\log B\times\dfrac{n}{D}\right)\right)=O(mn^{\frac{2}{3}}\log^{\frac{1}{3}}n)
空间复杂度：O(n+m)。
在线
等价于在线等价类分治，可能用 RT 树之类的黑科技解决。
时间复杂度应该会再多 1\sim2 只 \log。
11 区间排序全局逆序对
对每个顺序段开一棵动态开点权值线段树，然后用 ODT 暴力维护，线段树合并时传一下左侧右侧有多少个数即可统计贡献。
根据颜色段均摊，最多发生 O(n+m) 次线段树分裂。因为一次线段树分裂最多产生 O(\log n) 个节点，所以总共只会存在 O((n+m)\log n) 个节点。而每次线段树合并的代价是 O(\text{删除节点数})，所以总时间复杂度均摊 O((n+m)\log n)。
时间复杂度：O((n+m)\log n)。
12 区间排序前缀逆序对
前缀逆序对就是统计每个数前面有多少个数大于它，那么在权值线段树上再记录一下这个信息，发现每次线段树合并时再做一些区间加，时间复杂度显然还是正确的。
时间复杂度：O((n+m)\log n)。