本文共 1039 字，大约阅读时间需要 3 分钟。

经典CDQ分治题，求三维偏序

#include
   
    #include
    
     using namespace std;const int maxn=200000+200;struct Node{
   		int a,b,c;	int num,level;}node[maxn];bool cmp(Node A,Node B){
   		if(A.a==B.a&&A.b==B.b) return A.c
     
      0){
   				if(color[ind]==type) sum+=tree[ind];		ind-=lowbit(ind);	}	return sum;}void CDQ(int l,int r){
   		if(l==r) return ;	int mid=(l+r)>>1;	CDQ(l,mid);	CDQ(mid+1,r);	sort(node+l,node+mid+1,cmpcdq);	sort(node+mid+1,node+r+1,cmpcdq);	int i=l;	int j=mid+1;	type++;	for(;j<=r;j++){
   				for(;node[i].b<=node[j].b&&i<=mid;i++) Add(node[i].c,node[i].num);		node[j].level+=getSum(node[j].c); 	}}int main(){
   		scanf("%d%d",&n,&k);	for(int i=1;i<=n;i++){
   				int a,b,c;		scanf("%d%d%d",&a,&b,&c);		node[i]=Node{
   a,b,c,1,0};	}	sort(node+1,node+n+1,cmp);	tot=1;	for(int i=2;i<=n;i++){
   				if(node[i].a==node[tot].a&&node[i].b==node[tot].b&&node[i].c==node[tot].c) node[tot].num++;		else node[++tot]=node[i];	}	CDQ(1,tot);	for(int i=1;i<=tot;i++) ans[node[i].num+node[i].level-1]+=node[i].num;	for(int i=0;i
     
    
   

转载地址：https://kaven.blog.csdn.net/article/details/81150360 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！