[模板] CDQ分治

CDQ 分治是一种处理系列操作问题的一种离线算法，常数较小，可以代替一些因为内存原因无法使用的数据结构。

归并排序求逆序对

inline void merge(int l, int r){
if(l == r)
return;

int mid = (left + right) >> 1;

merge(l, mid);
merge(mid+1, r);

int i = l;
int j = mid+1;

for(register int k=l; k<=r; k++){
if((i <= mid && data[i] <= data[j]) || j > r)
tmp[k] = data[i++];
else{
tmp[k] = data[j++];
cnt += mid - i + 1;
}
}

for(register int k=l; k<=r; k++)
data[k] = tmp[k];
}


二维偏序问题

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 1500000 + 10;

int x = 0;
int p = 1;

char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return p ? x : (-x);
}

struct Statement{
int type;
int id;
int val;

bool operator < (const Statement x) const{
if(id == x.id)
return type < x.type;
return id < x.id;
}
}data[MAXN];

int n, m;
int cnt, query_cnt;
int ans[MAXN];
Statement tmp[MAXN];

inline void cdq(int l, int r){
int mid = (l + r) >> 1;

if(r == l)
return;

cdq(l, mid);
cdq(mid + 1, r);

int a = l, b = mid + 1;
int sum = 0;

for(register int k=l; k<=r; k++){
if((a <= mid && data[a] < data[b]) || b > r){
if(data[a].type == 1){
sum += data[a].val;
}
tmp[k] = data[a++];
}else{
if(data[b].type == 2){
ans[data[b].val] -= sum;
}else if(data[b].type == 3){
ans[data[b].val] += sum;
}
tmp[k] = data[b++];
}
}

for(register int k=l; k<=r; k++){
data[k] = tmp[k];
}

}
int main(){

for(register int i=1; i<=n; i++){
data[++cnt].type = 1;
data[cnt].id = i;
}

for(register int i=1; i<=m; i++){
int k = read();

if(k == 1){
data[++cnt].type = 1;
}else{
int x = read();
int y = read();

data[++cnt].type = 2;
data[cnt].id = x - 1;
data[cnt].val = ++query_cnt;

data[++cnt].type = 3;
data[cnt].id = y;
data[cnt].val = query_cnt;
}
}

cdq(1, cnt);

for(register int i=1; i<=query_cnt; i++){
printf("%d\n", ans[i]);
}

return 0;
}


三维偏序问题

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 800000 + 10;
const int MAXM = 500000 + 10;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}

int n, m;
int cnt, query_cnt;
int ans[MAXN];

struct Statement{
int type;
int x, y;
int w;
int val;

bool operator < (const Statement a) const{
if(x != a.x || y != a.y){
if(x == a.x)
return y < a.y;
return x < a.x;
}
return type < a.type;
}
}data[MAXN], tmp[MAXN];

struct BIT{
int num[MAXM];

inline int lowbit(int x){
return x & (-x);
}

inline void clear(int a){
while(a <= n){
if(num[a]){
num[a] = 0;
}else{
break;
}

a += lowbit(a);
}
}

inline void update(int a, int b){
while(a <= n){
num[a] += b;
a += lowbit(a);
}
}

inline int query(int a){
int ans = 0;

while(a){
ans += num[a];
a -= lowbit(a);
}

return ans;
}
}tree;

inline void cdq(int l, int r){
if(l == r)
return;

int mid = (l + r) >> 1;

cdq(l, mid);
cdq(mid + 1, r);

int a = l, b = mid + 1;

for(register int k=l; k<=r; k++){
if((a <= mid && data[a] < data[b]) || b > r){
if(data[a].type == 1){
tree.update(data[a].y, data[a].val);
}

tmp[k] = data[a++];
}else{
if(data[b].type == 2){
ans[data[b].val] += data[b].w * tree.query(data[b].y);
}

tmp[k] = data[b++];
}
}

for(register int k=l; k<=r; k++){
tree.clear(tmp[k].y);
data[k] = tmp[k];
}

}
int main(){

for(register int i=1; i<=m; i++){
int k = read();

if(k == 1){
data[++cnt].type = 1;
}else{
int a = read();
int b = read();
int c = read();
int d = read();

data[++cnt] = (Statement){2, c, d, 1, ++query_cnt};
data[++cnt] = (Statement){2, a-1, b-1, 1, query_cnt};
data[++cnt] = (Statement){2, c, b-1, -1, query_cnt};
data[++cnt] = (Statement){2, a-1, d, -1, query_cnt};
}
}

cdq(1, cnt);

for(register int i=1; i<=query_cnt; i++){
printf("%d\n", ans[i]);
}

return 0;
}