CDQ分治（仅为学习笔记）
一、名称由来
cdq分治来源于09年陈丹琦（cdq）大佬的国家队论文。
二、主要思想
二分之后，先处理前一区间，再用前一区间结果影响后一区间。
三、主要问题
求偏序问题，如：二维偏序、三维偏序。
四、直入主题 经典例题
三维偏序 （本人第一道紫题！）
题面：
有 n 个元素，第 i 个元素有 ai,bi,ci 三个属性，设 f(i) 表示满足 aj≤ai 且 bj≤bi 且 cj≤ci 且 j≠i 的 j 的数量。
对于 d∈[0,n]，求 f(i)=d 的数量。
三个属性，三维
解决思路：降维打击，将其分成一维一维来处理。
解决步骤：
1.处理第一维（结构体中a）：直接以第一维为主要关键字、第二维为次要关键字、第三维为第三关键字升序sort 排序。（平平无奇sort排）
bool cmp1(node x,node y)
{
if(x.a==y.a)
{
if(x.b==y.b)return x.c<y.c;
return x.b<y.b;
}
return x.a<y.a;
}
2.处理第二维（结构体中b）：归并思想 ，将已排好第一维的序列二分，使前一半与后一半始终处于s[j].a<=a[i].a(j<=mid<i) 再在两个区间分别以第二维为主要关键字、第三维为次 要关键字sort排。
bool cmp2(node x,node y)
{
if(x.b==y.b)return x.c<y.c;
return x.b<y.b;
}
1 void cdq(int l,int r)
2 {
3 if(l==r)return;
4 int mid=(l+r)/2;
5 cdq(l,mid);
6 cdq(mid+1,r);
7 sort(s+l,s+1+mid,cmp2);
8 sort(s+mid+1,s+1+r,cmp2);
9 int j=l;
10 for(int i=mid+1;i<=r;i++)
11 {
12 while(s[j].b<=s[i].b&&j<=mid)
13 {
14 add(s[j].c,s[j].sa);
15 j++;
16 }
17 s[i].ans+=qzh(s[i].c);
18 }
19 for(int i=l;i<j;i++)
20 add(s[i].c,-s[i].sa);
21 /*memset(w,0,sizeof(w));*/
22 //本来用的memset但要TLE
23 }
（才发现可以加行号）
1~8行为第二维的二分+排
3.处理第三维（结构体中c）：9~23行，在合并时处理，如果[l,mid]中有b<=[mid+1,r]中b的，则前一个元素可能为后一个元素的一个答案（或是一个前一项），此时将前一个元 素的第三维作为树状数组下标存入sa值；如果[l,mid]中b>[mid+1,r]中b，则前区间中当前元素之后所有元素b值皆大于后区间当前元素b值，不必继续查找，可以提出后区间当前元 素的答案，就为此时树状数组中的前缀和（可以用dp和树状数组的思维来理解吧）
lowbit：
int lowbit(int x)
{
return x&(-x);
}
加入树状数组：
void add(int x,int y)
{
while(x<=k)
{
w[x]+=y;
x+=lowbit(x);
}
}
提出s[i].ans前缀和：
int qzh(int x)
{
int e=0;
while(x>0)
{
e+=w[x];
x-=lowbit(x);
}
return e;
}
4.存答案：因题目中要求f(i)=d来存，就可以重新开一个数组（类似桶），对于一个下标i，它的答案就是它的ans值+x值，再根据题意转换一下存储方式就行了。
存答案：
for(int i=1;i<=m;i++)
anss[s[i].ans+s[i].sa-1]+=s[i].sa;
总结一下：难点易错点
1.刚存入时要排重，排重时应与后一位比较。
2.第一维用sort直接排，使后面归并排序时前一部分的第一维始终小于等于后一部分的第一维，消除第一维对处理的影响。
3.第二维在二分后sort排，起辅助比较作用。
4.第三维在合并时比较，作为树状数组的下标。
5.分情况讨论时，一种是将元素加入树状数组，一种是根据当前树状数组得出答案。
6.树状数组记得清零（因为是临时性的），并且不能用memset（要TLE）。
7.存储时要记得加上相同的元素。
噫，好了，上代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,w[200010],anss[200010],m=0,top=0;
struct node
{
int a,b,c,sa,ans;
//a、b、c:三属性
//sa:same前两字母，与之重复的元素
//ans:当前元素的答案（比它三属性皆小的）
};
node s[200010];
bool cmp1(node x,node y)
{
if(x.a==y.a)
{
if(x.b==y.b)return x.c<y.c;
return x.b<y.b;
}
return x.a<y.a;
}
bool cmp2(node x,node y)
{
if(x.b==y.b)return x.c<y.c;
return x.b<y.b;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
while(x<=k)
{
w[x]+=y;
x+=lowbit(x);
}
}
int qzh(int x)
{
int e=0;
while(x>0)
{
e+=w[x];
x-=lowbit(x);
}
return e;
}
void cdq(int l,int r)
{
if(l==r)return;
int mid=(l+r)/2;
cdq(l,mid);
cdq(mid+1,r);
sort(s+l,s+1+mid,cmp2);
sort(s+mid+1,s+1+r,cmp2);
int j=l;
for(int i=mid+1;i<=r;i++)
{
while(s[j].b<=s[i].b&&j<=mid)
{
add(s[j].c,s[j].sa);
j++;
}
s[i].ans+=qzh(s[i].c);
}
for(int i=l;i<j;i++)
add(s[i].c,-s[i].sa);
/*memset(w,0,sizeof(w));*/
//本来用的memset但要TLE
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
sort(s+1,s+1+n,cmp1);
for(int i=1;i<=n;i++)
{
top++;
if(s[i].a!=s[i+1].a||s[i].b!=s[i+1].b||s[i].c!=s[i+1].c)
//开始测试时一直出现问题，是因为用的s[i]和s[i-1]来比的，错误原因：
//与后一位比不同，意味着结束前一个进程（哪怕进程长度为1（与前后皆不同））；
//而与前一位比，top归零，未计数
{
m++;
s[m].a=s[i].a;
s[m].b=s[i].b;
s[m].c=s[i].c;
s[m].sa=top;
top=0;
}
}
cdq(1,m);
for(int i=1;i<=m;i++)
anss[s[i].ans+s[i].sa-1]+=s[i].sa;
for(int i=0;i<n;i++)//为什么0~n？看清题意d+1
printf("%d\n",anss[i]);
return 0;
}