CDQ分治
什么是CDQ分治？
CDQ分治是一种基于时间（其实不一定）的分治，最基本的运用是三位偏序。
三位偏序问题 [BZOJ3262]陌上花开
对于这个问题，我们先对点去重。
以第一维（花形）为第一关键字，第二维（颜色）为第二关键字，第三维（气味）为第三关键字，从小到大将点排序。
分治，回溯时处理答案
回溯时，将两个子序列以第二维（颜色）为第一关键字，第三维（气味）为第二关键字分别排序
通过左子序列更新右子序列的答案，记录两个下标(j~|~jepsilon[left,mid])，(i~|~iepsilon[mid+1,right])，从左向右移动，使得点(i)的颜色值（第二维）始终比点(j)的大。
如此一来，点(i)的花形值（第一维）始终比点(k~|~kepsilon[left,j])的大，点(i)的颜色值（第二维）始终比点(k~|~kepsilon[left,j])的大，所以只用求(sum_{k=left}^{j}k_{第三维}≤i_{第三维})的值即可，显然可以通过建立树状数组来存储。
由于每次都是通过左子序列更新右子序列的答案，所以一定不会有遗漏
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define maxn 100000
#define maxk 200000
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
void read(int &x){
int f=1;x=0;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
int n,k;
struct BIT{ //树状数组
int tree[maxk+5];
int lowbit(int x){return x&-x;}
void update(int x,int v){
for(int i=x;i<=k;i+=lowbit(i))
tree[i]+=v;
}
int query(int x){
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)) ans+=tree[i];
return ans;
}
} Tr;
struct node{
int x,y,z,i,cnt,ans;
node(){x=y=z=i=cnt=ans=0;}
friend bool operator==(node a,node b){return a.x==b.x&&a.y==b.y&&a.z==b.z;}
friend bool operator!=(node a,node b){return !(a==b);}
} A[maxn+5],w[maxn+5],s1[maxn+5];
int cnt=0;
bool cmp1(node a,node b){return a.x!=b.x?a.x<b.x:(a.y!=b.y?a.y<b.y:a.z<b.z);}
bool cmp2(node a,node b){return a.y!=b.y?a.y<b.y:a.z<b.z;}
void merge(node s[],int left,int right){
int mid=(left+right)/2;
int i=left,j=mid+1;
for(int k=left;k<=right;k++){
if(j>right||(i<=mid&&cmp2(s[i],s[j]))) s1[k]=s[i++];
else s1[k]=s[j++];
}
for(int k=left;k<=right;k++) s[k]=s1[k];
}
void uniq(node s1[],node s2[],int cnt1,int &cnt2){
cnt2=0;
for(int i=1;i<=cnt1;i++){
if(i==1||s1[i]!=s1[i-1]) s2[++cnt2]=s1[i];
else s2[cnt2].cnt+=s1[i].cnt;
}
}
void CDQ(int l,int r){
if(l==r) return;
int mid=(l+r)/2;
CDQ(l,mid),CDQ(mid+1,r);
merge(w,l,mid),merge(w,mid+1,r); //归并排序
int j=l-1;
for(int i=mid+1;i<=r;i++){
while(j<mid&&w[j+1].y<=w[i].y)
j++,Tr.update(w[j].z,w[j].cnt);
w[i].ans+=Tr.query(w[i].z);
}
for(int i=l;i<=j;i++)
Tr.update(w[i].z,-w[i].cnt);
}
int Ans[maxn+5];
int main(){
read(n),read(k);
for(int i=1;i<=n;i++) read(A[i].x),read(A[i].y),read(A[i].z),A[i].i=i,A[i].cnt=1;
sort(A+1,A+n+1,cmp1),uniq(A,w,n,cnt); //去重
CDQ(1,cnt),sort(w+1,w+cnt+1,cmp1);
for(int i=1;i<=cnt;i++) Ans[w[i].ans+w[i].cnt-1]+=w[i].cnt;
for(int i=0;i<n;i++) printf("%d
",Ans[i]);
}