瞎学了一下CDQ分治：大概算是一种思想，在分治时考虑一侧对另一侧的贡献，只能离线，如果有修改要求修改操作对询问的贡献独立，且修改之间互不影响
然后什么先按第一维排好序，之后分治中每层再按第二维排序，一边归并一边用权值树状数组统计第三维，注意一开始要去重
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=100005,M=200005; 6 struct D 7 { 8 int a,b,c,e,v; 9 }mem[N]; 10 int cnt[M],tra[M]; 11 int n,m,k; 12 bool cmp(D x,D y) 13 { 14 if(x.a!=y.a) return x.a<y.a; 15 else return x.b==y.b?x.c<y.c:x.b<y.b; 16 } 17 bool com(D x,D y) 18 { 19 return x.b==y.b?x.c<y.c:x.b<y.b; 20 } 21 void add(int p,int t) 22 { 23 while(p<=k) 24 tra[p]+=t,p+=p&-p; 25 } 26 int query(int p) 27 { 28 int ret=0; 29 while(p) 30 ret+=tra[p],p-=p&-p; 31 return ret; 32 } 33 void CDQ(int l,int r) 34 { 35 if(l==r) return; 36 int mid=(l+r)/2; 37 CDQ(l,mid),CDQ(mid+1,r); 38 sort(mem+l,mem+mid+1,com); 39 sort(mem+mid+1,mem+r+1,com); 40 int p1=mid+1,p2=l; 41 while(p1<=r) 42 { 43 while(p2<=mid&&mem[p2].b<=mem[p1].b) 44 add(mem[p2].c,mem[p2].e),p2++; 45 mem[p1].v+=query(mem[p1].c),p1++; 46 } 47 for(p1=l;p1<p2;p1++) 48 add(mem[p1].c,-mem[p1].e); 49 } 50 int main() 51 { 52 scanf("%d%d",&m,&k); 53 for(int i=1;i<=m;i++) 54 scanf("%d%d%d",&mem[i].a,&mem[i].b,&mem[i].c),mem[i].v=0; 55 sort(mem+1,mem+1+m,cmp),mem[m+1].a=mem[m+1].b=mem[m+1].c=-1; 56 for(int i=1,j=1;i<=m;i++,j++) 57 if(mem[i].a!=mem[i+1].a||mem[i].b!=mem[i+1].b||mem[i].c!=mem[i+1].c) 58 mem[++n]=mem[i],mem[n].e=j,j=0; 59 CDQ(1,n); 60 for(int i=1;i<=n;i++) 61 cnt[mem[i].v+mem[i].e-1]+=mem[i].e; 62 for(int i=0;i<m;i++) 63 printf("%d ",cnt[i]); 64 return 0; 65 }