#cdq分治
##一种奇妙的分治方法
- 优点:可以顶替复杂的高级数据结构;常数比较小。
-
缺点:必须离线操作。
CDQ分治的基本思想十分简单。如下:
我们要解决一系列问题,包含修改和查询操作,我们将这些问题排成一个序列,用一个区间[L,R]表示。
- 分。不用多说,递归处理左边区间[L,Mid]和右边区间[Mid+1,R]的问题。
- 治。核心。合并两个子问题,同时考虑到[L,Mid]内的修改对[Mid+1,R]内的查询产生的影响。即,用左边的子问题帮助解决右边的子问题。
$Wow,that’s $ sososo easy!easy!easy!
入门题:二维偏序(求逆序对):对于每个有序对(a,b)(a,b)(a,b),有多少个有序对(a2,b2)(a2,b2)(a2,b2)满足a2<aa2<aa2<a且b2>bb2>bb2>b
常规解法:树状数组,线段树。
经典解法:cdq分治。
我们在拿到所有有序对(a,b)(a,b)(a,b)的时候,先把aaa元素从小到大排序。这时候问题就变成了“求顺序对”,因为aaa元素已经有序,可以忽略aaa元素带来的影响,和“求逆序对”的问题是一样的。然后就可以各种乱搞了。
简单题:三维偏序:
BZOJ3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MB
Description
有n朵花,每朵花有三个属性:花形(s)、颜色©、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性
Output
包含N行,分别表示评级为0…N-1的每级花的数量。
Sample Input
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
Sample Output
3
1
3
0
1
0
1
0
0
1
常规解法:树套树。
经典解法:cdq分治+树状数组。
如果我们像二维偏序一样排序的话,那么可以保证aaa的有序,只需求b,cb,cb,c的逆序对,这个用树状数组维护即可。
代码如下:
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define maxk 200010
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(isdigit(ch)==0 && ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(int x){
int f=0;char ch[20];
if(!x){puts("0");return;}
if(x<0){putchar('-');x=-x;}
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar('\n');
}
typedef struct node{
int x,y,z,ans,w;
}stnd;
stnd a[maxn],b[maxn];
int n,cnt[maxk];
int k,n_;
bool cmpx(stnd u,stnd v){
if(u.x==v.x){
if(u.y==v.y)
return u.z<v.z;
return u.y<v.y;
}
return u.x<v.x;
}
bool cmpy(stnd u,stnd v){
if(u.y==v.y)
return u.z<v.z;
return u.y<v.y;
}
struct treearray{
int tre[maxk],kk;
int lwbt(int x){return x&(-x);}
int ask(int i){int ans=0; for(;i;i-=lwbt(i))ans+=tre[i];return ans;}
void add(int i,int k){for(;i<=kk;i+=lwbt(i))tre[i]+=k;}
}t;
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
sort(a+l,a+mid+1,cmpy);
sort(a+mid+1,a+r+1,cmpy);
int i=mid+1,j=l;
for(;i<=r;i++){
while(a[j].y<=a[i].y && j<=mid)
t.add(a[j].z,a[j].w),j++;
a[i].ans+=t.ask(a[i].z);
}
for(i=l;i<j;i++)
t.add(a[i].z,-a[i].w);
}
int main(){
n_=read(),k=read();t.kk=k;
for(int i=1;i<=n_;i++)
b[i].x=read(),b[i].y=read(),b[i].z=read();
sort(b+1,b+n_+1,cmpx);
int c=0;
for(int i=1;i<=n_;i++){
c++;
if(b[i].x!=b[i+1].x || b[i].y!=b[i+1].y || b[i].z!=b[i+1].z )
a[++n]=b[i],a[n].w=c,c=0;
}
cdq(1,n);
for(int i=1;i<=n;i++)cnt[a[i].ans+a[i].w-1]+=a[i].w;
for(int i=0;i<n_;i++)write(cnt[i]);
return 0;
}
不难发现,cdq分治起到了一个降维的作用,这在我们处理复杂的问题时有显著的作用。