概述

cdq分治是非常厉害的一种分治方法
主要思想就是用[L,m]的操作来更新[m+1,R]的询问
广泛应用于偏序问题的降维
或者满足用前一段更新后一段性质的东西

题目

hdu5126

每次操作在 (x,y,z) 添加一个点
每次询问在 (x1,y1,z1)(x2,y2,z2) 之间的点数

经典的四(3+1)维偏序问题

时间一维有序,用cdq降掉x,y两维,z离散化后用树状数组统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define R(i,n) for(int i=0;i<(n);++i)
#define fill(a,b) memset(a,b,sizeof(a))
#define pb push_back

const int maxn = 5e4 + 10;

struct Q{
int x,y,z;
int ty,id;
};

vector<Q> op,op1,op2;
vector<int> allZ;
bool isA[maxn];
int bit[2*maxn];
int ans[maxn];

bool cmp1(const Q& a,const Q& b)
{
if(a.x == b.x) return a.id < b.id;
return a.x < b.x;
}

bool cmp2(const Q& a,const Q& b)
{
if(a.y == b.y) return a.id < b.id;
return a.y < b.y;
}

void add(int x,int v)
{
for(;x < 2*maxn;x += x&-x) bit[x] += v;
}

int query(int x)
{
int res = 0;
for(; x; x -= x&-x) res += bit[x];
return res;
}

void count()
{
R(i,op2.size())
if(!op2[i].ty) add(op2[i].z,1);
else ans[op2[i].id] += query(op2[i].z)*op2[i].ty;
R(i,op2.size()) if(!op2[i].ty) add(op2[i].z,-1);
}

void CDQ1(int L,int R)
{
if(L >= R) return;
int m = (L+R) >> 1;
CDQ1(L,m);
op2.clear();
F(i,L,m) if(!op1[i].ty) op2.push_back(op1[i]);
F(i,m+1,R) if(op1[i].ty) op2.push_back(op1[i]);
sort(op2.begin(),op2.end(),cmp2);
count();
CDQ1(m+1,R);
}

void CDQ(int L,int R)
{
if(L >= R) return;
int m = (L+R) >> 1;
CDQ(L,m);
op1.clear();
F(i,L,m) if(!op[i].ty) op1.push_back(op[i]);
F(i,m+1,R) if(op[i].ty) op1.push_back(op[i]);
sort(op1.begin(),op1.end(),cmp1);
CDQ1(0,op1.size() - 1);
CDQ(m+1,R);
}

void init()
{
fill(ans,0);
fill(isA,0);
fill(bit,0);
allZ.clear();
op.clear();
}

int main()
{
//freopen("test.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
init();
int n;
scanf("%d",&n);
R(i,n)
{
int ty,x[2],y[2],z[2];
scanf("%d %d %d %d",&ty,x,y,z);
if(ty == 1)
{
op.pb((Q){x[0],y[0],z[0],0,i});
allZ.pb(z[0]);
}
else
{
scanf("%d %d %d",x+1,y+1,z+1);
isA[i] = 1;
op.pb((Q){x[0]-1,y[0]-1,z[0]-1,-1,i});
op.pb((Q){x[0]-1,y[0]-1,z[1],1,i});
op.pb((Q){x[0]-1,y[1],z[0]-1,1,i});
op.pb((Q){x[0]-1,y[1],z[1],-1,i});
op.pb((Q){x[1],y[0]-1,z[0]-1,1,i});
op.pb((Q){x[1],y[0]-1,z[1],-1,i});
op.pb((Q){x[1],y[1],z[0]-1,-1,i});
op.pb((Q){x[1],y[1],z[1],1,i});

allZ.pb(z[0]-1);
allZ.pb(z[1]);
}
}
sort(allZ.begin(),allZ.end());
int qn = unique(allZ.begin(),allZ.end()) - allZ.begin();
R(i,op.size()) op[i].z = lower_bound(allZ.begin(),allZ.end(),op[i].z) - allZ.begin() + 1;
CDQ(0,op.size()-1);
R(i,n) if(isA[i]) printf("%d\n",ans[i]);
}
return 0;
}

hdu4742

三维LIS,而且要统计LIS数目

对x一维排序
对y一维进行cdq分治
对z一维离散化后用树状数组统计

对于答案可以开两维进行更新,第一维为长度,第二维为数量
更新时若长度相等则将数量相加

hdu5730

cdq分治 + FFT

dp的形式就是用前n段的卷积更新第n+1段

参考