cdq分治
cdq分治是cdq创造的一种分治算法，分治的思想就是划分问题，解决子问题，合并答案
cdq分治则是在合并子区间时，考虑左区间对右区间的影响，换言之，cdq分治解决的是前对后（按某种顺序）的单向影响的问题。
例题
题目背景
这是一道模板题，可以使用 bitset，CDQ 分治，KD-Tree 等方式解决。
题目描述
有 n 个元素，第 ii 个元素有
ai,bi,ci 三个属性，设 f(i) 表示满足
aj≤ai 且 bi≤bj 且
cj≤ci 且 i≠j的i 和j 的数量。
对于 d∈[0,n)，求 f(i) = d的数量。
输入格式
第一行两个整数 n,k 表示元素数量和最大属性值。
接下来 n行，每行三个整数 ai
,bi,ci，分别表示三个属性值。
输出格式
n 行，第 d+1 行表示 f(i) = d 的 i 的数量。
输入输出样例
输入 #1
| 10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
|
输出 #1
说明/提示
1≤n≤105，1≤ai,bi,ci≤k≤2×105。
代码
参考了luogu的这篇博客
用我的语言整理一番
首先二维偏序的问题我们可以用树状数组轻松解决和求偏序的问题是相同的。
那么考虑三维比二维多一维，我们进行按其中一维排序然后分治，在这一维度左区间就比右区间小，考虑到我们的子问题分到了每一个元素，那么我们合并后就天然地解决了一维。这样，我们再将每个区间按省下两维排序，以求二维偏序的方法求一遍就可以解决这个问题。
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
| #include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=2e5+10;
struct node {
int x,y,z,ans,cnt;
} a1[N],a2[N];
bool cmp1(node a,node b) {
if(a.x==b.x) {
if(a.y==b.y)return a.z<b.z;
return a.y<b.y;
}
return a.x<b.x;
}
bool cmp2(node a,node b) {
if(a.y==b.y)return a.z<b.z;
return a.y<b.y;
}
int c[N],ans[N];
int n,k,m=0;
int lowbit(int x){
return x&(-x);
}
void update(int x,int w){
while(x<=k){
c[x]+=w;
x+=lowbit(x);
}
}
int query(int x){
int ret=0;
while(x){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void cdq(int l,int r) {
if(l==r)return;
int mid=(l+r)/2;
cdq(l,mid);
cdq(mid+1,r);
sort(a2+l,a2+mid+1,cmp2);
sort(a2+mid+1,a2+r+1,cmp2);
int i,j=l;
for(i=mid+1; i<=r; ++i) {
while(a2[i].y>=a2[j].y&&j<=mid) {
update(a2[j].z,a2[j].cnt);
j++;
}
a2[i].ans+=query(a2[i].z);
}
for(int i=l;i<j;i++)update(a2[i].z,-a2[i].cnt);
}
int main() {
IOS
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>a1[i].x>>a1[i].y>>a1[i].z;
}
sort(a1+1,a1+1+n,cmp1);
int top=0;
for(int i=1; i<=n; i++) {
top++;
if(a1[i].x!=a1[i+1].x||a1[i].y!=a1[i+1].y||a1[i].z!=a1[i+1].z) {
a2[++m].x=a1[i].x;
a2[m].y=a1[i].y;
a2[m].z=a1[i].z;
a2[m].cnt=top;
top=0;
}
}
cdq(1,m);
for(int i=1;i<=m;i++){
ans[a2[i].ans+a2[i].cnt-1]+=a2[i].cnt;
}
for(int i=0;i<n;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
|