逆序对问题的总结
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)。
- 三维/更高维支配对：？？？
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(n\sqrt n)
空间复杂度：O(n\sqrt n)
离线
P5047
莫队二次离线。
时间复杂度：O(n\sqrt n)
空间复杂度：O(n)
5 单点修改区间逆序对
题目
无
在线
二维分块。
修改时考虑如何维护上面这些信息。
$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(n\sqrt n)
空间复杂度：O(n\sqrt n)
离线
暂时不会非常优秀的做法。
6 区间覆盖区间逆序对
应该是 #3 和 #5 的做法揉在一起，然后是 O(n\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 三维/更高维支配对
应该可做，但暂时不会做法。
我感觉 k 维有 O(n\log^{k-1}n+n\sqrt n) 的做法。