CDQ分治小結 warning:此文僅用博主複習使用，初學者看的話後果自負。。 複習的時候才發現以前根本就沒寫過這種東西的總結，簡單的扯一扯 cdq分治的經典應用就是解決偏序問題 比如最經典的三維偏序問題 給出$n$個數，每個數$i$，有三個屬性$a_i, b_i, c_i$，現在我們要統計對於每個 ...
CDQ分治小結
warning:此文僅用博主複習使用，初學者看的話後果自負。。
複習的時候才發現以前根本就沒寫過這種東西的總結，簡單的扯一扯
cdq分治的經典應用就是解決偏序問題
比如最經典的三維偏序問題
給出\(n\)個數，每個數\(i\)，有三個屬性\(a_i, b_i, c_i\)，現在我們要統計對於每個\(i\)，\(a_j \leqslant a_i, b_j \leqslant b_i, c_j \leqslant c_i\)的個數
顯然我們可以先把所有數都按\(a_i\)排序一遍，這樣考慮每個位置\(i\)的時候只需要考慮它前面的貢獻即可
接下來我們遞歸處理區間\([1, N]\)。
設分治中心為\(mid\)，cdq分治的主要思想遞歸處理每一段區間，只考慮過分治中心的貢獻。
同時，我們採用歸併排序的思想，保證每一次統計答案的時候區間\([l, mid]\)和\([mid +1, r]\)內的元素的\(b_i\)都是相對有序的
這樣我們只需要用兩個指針掃一遍，同時用樹狀數組來維護一下\(c_i\)即可
好像說的挺抽象的，貌似直接看代碼會好很多？
void CDQ(int l, int r) {
if(l >= r) return ;//區間不合法
int mid = l + r >> 1;
CDQ(l, mid); CDQ(mid + 1, r);//遞歸下去處理子區間，處理完之後保證區間內的bi相對有序
int nl = l, nr = mid + 1, top = l - 1, sum = 0;//使用兩個指針來歸併本區間
while(nl <= mid || nr <= r) {//st數組記錄的時把兩端區間按bi大小合併後的值
if((nr > r) || (nl <= mid && A[nl].b <= A[nr].b)) T.add(A[nl].c, A[nl].w), st[++top] = A[nl++];//用樹狀數組維護ci的貢獻
else A[nr].id += T.Query(A[nr].c ), st[++top] = A[nr++];//直接查詢即可
}
for(int i = l; i <= mid; i++) T.add(A[i].c, -A[i].w);//把左邊區間的影響消除
for(int i = l; i <= r; i++) A[i] = st[i];//按bi排序
}然而有一種非常噁心的情況：即\(a_i = a_j, b_i = b_j, c_i = c_j\)
他們內部的貢獻往往是不好考慮的，一個最直觀的想法是直接把這些相同的數看成一個，統計答案的時候直接加上他們的數量即可
模板
#include<bits/stdc++.h>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
const int MAXN = 2e5 + 10;
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
char obuf[1<<24], *O=obuf;
void print(int x) {
if(x > 9) print(x / 10);
*O++= x % 10 + '0';
}
int N, ans[MAXN];
struct Array {
int a, b, c, id, w;
bool operator == (const Array &rhs) const {
return a == rhs.a && b == rhs.b && c == rhs.c;
}
bool operator < (const Array &rhs) const {
return(a == rhs.a ? (b == rhs.b ? c < rhs.c : b < rhs.b) : a < rhs.a);
}
}A[MAXN], st[MAXN];
struct Node {
#define lb(x) (x & (-x))
int T[MAXN], Lim;
void add(int x, int v) {
while(x <= Lim) T[x] += v, x += lb(x);
}
int Query(int x) {
int ans = 0;
while(x) ans += T[x], x -= lb(x);
return ans;
}
}T;
void CDQ(int l, int r) {
if(l >= r) return ;
int mid = l + r >> 1;
CDQ(l, mid); CDQ(mid + 1, r);
int nl = l, nr = mid + 1, top = l - 1, sum = 0;
while(nl <= mid || nr <= r) {
if((nr > r) || (nl <= mid && A[nl].b <= A[nr].b)) T.add(A[nl].c, A[nl].w), st[++top] = A[nl++];
else A[nr].id += T.Query(A[nr].c ), st[++top] = A[nr++];
}
for(int i = l; i <= mid; i++) T.add(A[i].c, -A[i].w);
for(int i = l; i <= r; i++) A[i] = st[i];
}
int main() {
N = read(); T.Lim = read();
for(int i = 1; i <= N; i++) A[i].a = read(), A[i].b = read(), A[i].c = read(), A[i].w = 1;
stable_sort(A + 1, A + N + 1);
int num = 1;
for(int i = 2; i <= N; i++){
if(A[i] == A[num]) A[num].w++;
else A[++num] = A[i];
}
CDQ(1, num);
for(int i = 1; i <= num; i++) ans[A[i].id + A[i].w - 1] += A[i].w;
for(int i = 0; i < N; i++) print(ans[i]), *O++ = '\n';
fwrite(obuf, O-obuf, 1 , stdout);
return 0;
}
