CDQ分治是一種離線分治演算法，它基于時間順序對操作序列進行分治，
看這樣一個問題： 在一個三維坐標系中，有若干個點，每個點都有對應的坐標 \((X_i , Y_i , Z_i)\) ，我們要對于每個點求所有滿足 \(X_j <=X_i, Y_j <= Y_i , Z_j <= Z_i\) 的 j 的數量，
考慮在二維平面上怎么做：我們可以將所有點按照 X 坐標排序，再用一個樹狀陣列或者其他資料結構維護 Y 坐標，每次讀到一個點就統計答案，然后將這個點加入樹狀陣列，這樣可以同時保證 X，Y 坐標都滿足條件，
如果這時再多一維，我們就沒辦法再用這種方法排序了，按照一維排序必然會打亂另外兩維，這時我們考慮CDQ分治，先按 X 坐標排序，然后對序列進行分治，每次分出左右兩段子序列，這時我們可以發現，左序列中每個點的 X 坐標小于右序列中點的 X 坐標，這時分別將左右序列按照 Y 坐標排序，統計答案時，只更新右序列中點的答案，只在樹狀陣列中加入左序列的點，
模版： P3810 【模板】三維偏序（陌上花開）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100005;
const int M = 200005;
int C[M], n, maxk, nn, ans[N];
struct node {
int a, b, c, tot, num;
} e[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for(; x <= maxk; x += lowbit(x)) C[x] += k;
}
int query(int x) {
int answ = 0;
for(; x; x -= lowbit(x)) answ += C[x];
return answ;
}
bool cmp1(node x, node y) {
if(x.a == y.a && x.b == y.b) return x.c < y.c;
if(x.a == y.a) return x.b < y.b;
return x.a < y.a;
}
void cdq(int l, int r) {
int mid = (l + r) >> 1;
if(l != mid) cdq(l, mid);
if(mid + 1 != r) cdq(mid + 1, r);
node p[N];
int pt = 0, i = l, j = mid + 1;
while(i <= mid && j <= r) {//對于第二維歸并排序
if(e[i].b <= e[j].b) add(e[i].c, e[i].tot), p[++pt] = e[i++];//插入
else e[j].num += query(e[j].c), p[++pt] = e[j++];//更新答案
}
while(i <= mid) add(e[i].c, e[i].tot), p[++pt] = e[i++];
while(j <= r) e[j].num += query(e[j].c), p[++pt] = e[j++];
for(int t = l; t <= mid; t++) add(e[t].c, -e[t].tot);//樹狀陣列清空
for(int t = 1, u = l; t <= pt && u <= r; t++, u++) e[u] = p[t];//更新序列
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d%d", &nn, &maxk);
for(int i = 1, a, b, c; i <= nn; i++) {
scanf("%d%d%d", &a, &b, &c);
e[i].a = a, e[i].b = b, e[i].c = c;
e[i].num = 0; e[i].tot = 1;
}
sort(e + 1, e + 1 + nn, cmp1);//先按照第一維排序
n = 1;
for(int i = 2; i <= nn; i++) {
if(e[i].a == e[n].a && e[i].b == e[n].b && e[i].c == e[n].c) e[n].tot++;
else e[++n] = e[i];
}
cdq(1, n);
for(int i = 1; i <= n; i++) {
ans[e[i].num + e[i].tot - 1] += e[i].tot;
}
for(int i = 0; i < nn; i++) printf("%d\n", ans[i]);
return 0;
}
例題1 : P3157 [CQOI2011]動態逆序對
考慮如和將其轉化為三維偏序問題，我們要計算洗掉一個點對答案對貢獻，即洗掉的這個點左邊比它大的點的數量和右邊比他小的點的數量，這樣三維分別是洗掉順序，序列中位置，元素大小，
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long lld;
const int N = 100005;
const int M = 50005;
int n, m, pos[N], ansper[N], ansnxt[N];
struct node {
int x, y, type;
} e[N], a[N];
int C[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for(; x < N; x += lowbit(x)) C[x] += k;
}
int query(int x) {
int summ = 0;
for(; x; x -= lowbit(x)) summ += C[x];
return summ;
}
void cdq_per(int l, int r) {
if(l == r) return ;
int mid = (l + r) >> 1;
cdq_per(l, mid); cdq_per(mid + 1, r);
node p[N];
int i = l, j = mid + 1, pt = 0;
while(i <= mid && j <= r) {
if(e[i].x <= e[j].x) add(e[i].y, 1), p[++pt] = e[i++];
else {
if(e[j].type == 0) p[++pt] = e[j++];
else ansper[e[j].type] += query(N - 1) - query(e[j].y), p[++pt] = e[j++];
}
}
while(i <= mid) add(e[i].y, 1), p[++pt] = e[i++];
while(j <= r) {
if(e[j].type == 0) p[++pt] = e[j++];
else ansper[e[j].type] += query(N - 1) - query(e[j].y), p[++pt] = e[j++];
}
for(int k = l; k <= mid; k++) add(e[k].y, -1);
for(int t = 1, u = l; t <= pt && u <= r; t++, u++) e[u] = p[t];
}
void cdq_nxt(int l, int r) {
if(l == r) return ;
int mid = (l + r) >> 1;
cdq_nxt(l, mid); cdq_nxt(mid + 1, r);
node p[N];
int i = l, j = mid + 1, pt = 0;
while(i <= mid && j <= r) {
if(a[i].x <= a[j].x) add(a[i].y, 1), p[++pt] = a[i++];
else {
if(a[j].type == 0) p[++pt] = a[j++];
else ansnxt[a[j].type] += query(a[j].y), p[++pt] = a[j++];
}
}
while(i <= mid) add(a[i].y, 1), p[++pt] = a[i++];
while(j <= r) {
if(a[j].type == 0) p[++pt] = a[j++];
else ansnxt[a[j].type] += query(a[j].y), p[++pt] = a[j++];
}
for(int k = l; k <= mid; k++) add(a[k].y, -1);
for(int t = 1, u = l; t <= pt && u <= r; t++, u++) a[u] = p[t];
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1, x; i <= n; i++) {
scanf("%d", &x);
e[i].x = e[i].type = 0; e[i].y = x;
pos[x] = i;
}
for(int i = 1, x; i <= m; i++) {
scanf("%d", &x);
e[pos[x]].x = m - i + 1;
e[pos[x]].type = i;
}
for(int i = 1; i <= n; i++) a[i] = e[n - i + 1];
cdq_per(1, n);
for(int i = 1; i <= n; i++) e[i] = a[n - i + 1];
cdq_nxt(1, n);
lld ans_sum = 0;
for(int i = 1; i <= n; i++) {
ans_sum += i - query(e[i].y) - 1;
add(e[i].y, 1);
}
int k = 1;
while(k <= m) {
printf("%lld\n", ans_sum);
ans_sum -= (ansper[k] + ansnxt[k]);
k++;
}
return 0;
}
例題2 ： P4169 [Violet]天使玩偶/SJY擺棋子
，，，，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85167.html
標籤：其他
上一篇：資料結構-線性結構
下一篇：《演算法導論》第二章筆記