萌新 CDQ TLE求调

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5,K=2e5+5;
int n,k,tree[K],ans_rank[N],cnt_point,tmp_data;
struct Point{
	int x,y,z,k,ans;
}point[N];

struct Data{
	int x,y,z;
}data[N];

bool cmp_data(Data a,Data b){
	if(a.x==b.x){
		if(a.y==b.y) return a.z<b.z;
		return a.y<b.y;
	}
	return a.x<b.x;
}

bool cmp_point_x(Point a,Point b){
	if(a.x==b.x){
		if(a.y==b.y) return a.z<b.z;
		return a.y<b.y;
	}
	return a.x<b.x;
}

bool cmp_point_y(Point a,Point b){
	if(a.y==b.y) return a.z<b.z;
	return a.y<b.y;
}

void init(){
	for(int i=0;i<K;i++) tree[i]=0;
}

int lowbit(int x){
	return x&(-x);
}

void add(int x,int y){
	while(x<=k){
		tree[x]+=y;
		x+=lowbit(x);
	}
}

int query(int x){
	int tmp=0;
	while(x>0){
		tmp+=tree[x];
		x-=lowbit(x);
	}
	return tmp;
}

void query(int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	query(l,mid);
	query(mid+1,r);
	sort(point+l,point+mid+1,cmp_point_y);
	sort(point+mid+1,point+r+1,cmp_point_y);
	int s=l;
	for(int t=mid+1;t<=r;t++){
		while(s<=mid && point[s].y<=point[t].y){
			add(point[s].z,point[s].k);
			s++;
		}
		point[t].ans+=query(point[t].z);
	}
	while(s<=mid){
		add(point[s].z,point[s].k);
		s++;
	}
	init();
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%d%d%d",&data[i].x,&data[i].y,&data[i].z);
	sort(data,data+n,cmp_data);
	for(int i=0;i<n;i++){
		if(data[i].x==data[i+1].x && data[i].y==data[i+1].y && data[i].z==data[i+1].z) continue;
		point[cnt_point].x=data[i].x;
		point[cnt_point].y=data[i].y;
		point[cnt_point].z=data[i].z;
		point[cnt_point].k=i-tmp_data+1;
		tmp_data=i+1;
		cnt_point++;
	}
	query(0,cnt_point-1);
	for(int i=0;i<cnt_point;i++) ans_rank[point[i].ans+point[i].k-1]+=point[i].k;//
	for(int i=0;i<n;i++) printf("%d\n",ans_rank[i]);
}