1.cdcq分治
其实是cdcq在“分治与倍增”讲了一回cdq分治（从而被lg网校叫做cdcq分治。
主要思想一张图：
比方说三维偏序。
先排序一下（x,y,z 为 \(1,2,3\) 关键字），解决 x 问题。
去一下重。
然后cdcq分治：
如果 \(l\ge r\)，返回；
先递归左右；
将左右排序(y,z 为 \(1,2\) 关键字)。可以发现跨区间时这样不会影响 x 的有序性。
然后双指针。设 l 在左区间左端点，r 在右区间左端点。很明显 l,r 满足双指针性质。
枚举右端点。如果 l 的 y 小于 r 的 y，那么将 l 的 z 插入值域树状数组。\(l\gets l+1\)。
每个右端点的贡献为树状数组中在该右端点及右端点左边的个数。
记得搞完之后清空。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=1e5+5,maxk=2e5+5;
int c[maxk];
struct p{
int a,b,c,cnt,ans;
}s1[maxn],s2[maxn];
bool cmp1(p x,p y){
return x.a==y.a?((x.b==y.b)?x.c<y.c:x.b<y.b):x.a<y.a;
}
bool cmp2(p x,p y){
return (x.b==y.b)?x.c<y.c:x.b<y.b;
}
void add(int p,int x){
for(;p<=k;p+=p&(-p))c[p]+=x;
//cout<<"fucks"<<endl;
}
int sum(int p){
int res=0;
for(;p;p-=p&(-p))res+=c[p];
return res;
}
int Ans[maxn];
void cdq(int l,int r){
if(l==r)return ;
int mid=l+r>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(s2+l,s2+mid+1,cmp2);
sort(s2+mid+1,s2+r+1,cmp2);
int j=l;
for(int i=mid+1;i<=r;i++){
while(s2[i].b>=s2[j].b&&j<=mid){
add(s2[j].c,s2[j].cnt);
++j;
}
s2[i].ans+=sum(s2[i].c);
}
for(int i=l;i<j;i++)add(s2[i].c,-s2[i].cnt);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>s1[i].a>>s1[i].b>>s1[i].c;
}
sort(s1+1,s1+n+1,cmp1);
int las=0,m=0;
for(int i=1;i<=n;i++){
las++;
if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c){
s2[++m].a=s1[i].a,s2[m].b=s1[i].b,s2[m].c=s1[i].c,s2[m].cnt=las;
las=0;
}
}
cdq(1,m);
for(int i=1;i<=m;i++){
Ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
}
for(int i=0;i<n;i++)cout<<Ans[i]<<endl;
return 0;
}