前言
昨天写一个数据结构题……大致就是给出一个排列，每次删除一个数字，求每次删除之前的逆序对数目。
不难发现，这个问题是动态的二维偏序，我们可以把它转为三维数点。不妨假设在某个二维平面中有一个坐标系，横坐标为排列中的下标，纵坐标为排列中的值，也就是排列中一个数 $a_i$ 对应坐标 $(i, a_i)$ 。先用树状数组求出初始逆序对数目，每次删点 $(x, y)$ 后减少的逆序对数目即为 $(1, n) - (x-1, y+1)$ 和 $(x+1, y-1) - (n, 1)$ 的点数。动态等价于多了时间一维，于是就转为了三维数点。类比二维数点的线段树+扫描线做法，三维数点可以用二维线段树+扫描线做。扫描线顺着时间维度扫，并相应修改二维线段树即可。
然而空间是 $O(n \lg^2n)$ 的，MLE了……
又写树状数组套平衡树，发现卡常数，卡成80.
不服，又写树状数组套动态开点线段树，发现居然还卡常数，卡成90……
于是学一波CDQ分治，听说能轻松水过= =
UPD:的确是轻松水过qwq
二维偏序
求逆序对
在归并排序的时候统计。归并排序是自底向上地把下标的有序性逐步转变为值的有序性的过程。分治的时候，只有左右的值有了有序性，同时左边的值在另一种偏序关系下，都小于右边的值，才能方便地统计答案。当 $[l, m), [m, r)$ 都排好序的时候，每次在选取右边元素的时候，累加 $m - p_l$ 的答案即可。
在偏序之间转化，每次利用方便统计答案的偏序关系分治处理，在合并的时候计算左边区间对右边的贡献，是 CDQ 分治的基本思路。
代替树状数组（动态一维数点）
CDQ 分治可以离线代替树状数组。
输入时满足时间有序，但是树状数组有求区间和的操作，而区间求和转为前缀和后，只有下标有序才方便统计答案。逐步按照下标归并排序。注意到下标相同的时候，对于右半区间的某个询问，需要处理完左区间所有的下标小于等于该询问下标的修改（显然左区间中修改时间都在该询问之前），这个询问才能完整地回答。为了保证上述性质，归并排序的比较条件为：以下标为第一关键字，下标相同的时候，修改优先。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5, MAXQ = (MAXN<<2) + 10;
struct Query {
int type, idx, val;
bool operator<(const Query &rhs) const {
return idx == rhs.idx ? (type == 1 && rhs.type > 1) : idx < rhs.idx;
}
};
Query qry[MAXQ+10], T[MAXQ+10];
int n, q, qcnt, acnt, ans[MAXQ+10];
inline int readint() {
int f=1, r=0; char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
return f*r;
}
void solve(int L, int R) { // [L, R)
if(R - L <= 1) return;
int M = (L + R) / 2, p = L, pl = L, pr = M, sum = 0;
solve(L, M); solve(M, R);
while(pl < M || pr < R) {
if(pr >= R || (pl < M && qry[pl] < qry[pr])) {
if(qry[pl].type == 1)
sum += qry[pl].val;
T[p++] = qry[pl++];
} else {
if(qry[pr].type == 2)
ans[qry[pr].val] -= sum;
else if(qry[pr].type == 3)
ans[qry[pr].val] += sum;
T[p++] = qry[pr++];
}
}
for(int i = L; i < R; i++)
qry[i] = T[i];
}
void init() {
int op, a, b;
n = readint(); q = readint();
for(int i = 0; i < n; i++)
qry[qcnt++] = (Query){ 1, i, readint() };
for(int i = 0; i < q; i++) {
op = readint();
switch(op) {
case 1:
a = readint(); b = readint();
qry[qcnt++] = (Query){ 1, a-1, b };
break;
case 2:
a = readint(); b = readint();
qry[qcnt++] = (Query){ 2, a-2, acnt };
qry[qcnt++] = (Query){ 3, b-1, acnt };
acnt++;
break;
}
}
}
void work() {
solve(0, qcnt);
for(int i = 0; i < acnt; i++)
printf("%d\n", ans[i]);
}
int main() {
init(); work();
return 0;
}
三维偏序
求广义逆序对
其实就是求空间中满足 $a_i < a, b_i < b, c_i < c$ 的点数。我不知道这个叫啥名字，就随便取一个啦。
其实叫做广义的逆序对也是有道理的，因为只不过是把归并排序的直接统计答案变成了使用权值树状数组统计答案。代码和归并排序基本是一样的= =
根据上面对二维偏序的讨论，权值树状数组也可以换成另一层 CDQ 分治，也就是说这个问题用 CDQ 分治套 CDQ 分治也是可以解决的。
代码：
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
struct Point {
int x, y, z, idx;
bool operator<(const Point &rhs) const {
return x == rhs.x ?
(y == rhs.y ?
z < rhs.z : y < rhs.y)
: x < rhs.x;
}
bool operator==(const Point &rhs) const {
return x == rhs.x && y == rhs.y && z == rhs.z;
}
};
struct Query {
int type, x, y, z, idx;
bool operator<(const Query &rhs) const {
return y == rhs.y ? type < rhs.type : y < rhs.y;
}
};
const int MAXN = 4e5;
int n, k, qcnt, ans[MAXN+10], totv[MAXN+10], anscnt[MAXN+10], bit[MAXN+10];
map<Point, int> PCnt; Query qry[MAXN+10], T[MAXN+10];
inline int readint() {
int f=1, r=0; char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
return f*r;
}
void init() {
int x, y, z;
n = readint(); k = readint();
for(int i = 1; i <= n; i++) {
x = readint(); y = readint(); z = readint();
PCnt[(Point){ x, y, z, i }]++;
}
for(map<Point, int>::iterator it = PCnt.begin();
it != PCnt.end(); ++it) {
qry[++qcnt] = (Query) { 1, it->fst.x, it->fst.y, it->fst.z, it->fst.idx };
qry[++qcnt] = (Query) { 2, it->fst.x, it->fst.y, it->fst.z, it->fst.idx };
totv[it->fst.idx] = it->snd; ans[it->fst.idx] = -(it->snd);
}
}
inline int lowbit(int x) { return x & (-x); }
inline int qsum(int p) {
int ret = 0;
while(p > 0) {
ret += bit[p];
p -= lowbit(p);
}
return ret;
}
inline void add(int p, int val) {
while(p <= k) {
bit[p] += val;
p += lowbit(p);
}
}
void solve(int L, int R) {
if(R <= L + 1) return;
int M = (L + R) / 2, p = L, pl = L, pr = M;
solve(L, M); solve(M, R);
while(pl < M || pr < R) {
if(pr >= R || (pl < M && qry[pl] < qry[pr])) {
if(qry[pl].type == 1)
add(qry[pl].z, totv[qry[pl].idx]);
T[p++] = qry[pl++];
} else {
if(qry[pr].type == 2)
ans[qry[pr].idx] += totv[qry[pr].idx] * qsum(qry[pr].z);
T[p++] = qry[pr++];
}
}
pl = L, pr = M;
while(pl < M || pr < R) {
if(pr >= R || (pl < M && qry[pl] < qry[pr])) {
if(qry[pl].type == 1)
add(qry[pl].z, -totv[qry[pl].idx]);
pl++;
} else pr++;
}
for(int i = L; i < R; i++) qry[i] = T[i]; // 一定最后再copy！！！！！！！
}
bool cmp(const Query &lhs, const Query &rhs) {
return lhs.x == rhs.x ? lhs.type < rhs.type : lhs.x < rhs.x;
}
void work() {
sort(qry + 1, qry + qcnt + 1, cmp);
solve(1, qcnt + 1);
for(int i = 1; i <= n; i++) {
if(!totv[i]) continue;
anscnt[ans[i] / totv[i]] += totv[i];
}
for(int i = 0; i < n; i++)
printf("%d\n", anscnt[i]);
}
int main() {
init(); work();
return 0;
}
动态二维数点
其实类似于求广义逆序对= = 做个二维前缀和就好了
