CDQ分治求调
查看原帖
CDQ分治求调
442116
qweradf楼主2023/10/18 19:21

感觉问题出在重复点的处理上,求大佬们帮忙看看qwq

#include<bits/stdc++.h>
using namespace std;
int n,k;
struct point{
	int x,y,z,id,cnt;
	bool t;
}p[100005],t[100005];
bool cmpx(point u,point v){
	if(u.x==v.x){if(u.y==v.y) return u.z<v.z; return u.y<v.y;} return u.x<v.x;
}
bool cmpy(point u,point v){if(u.y==v.y){if(u.z==v.z) return u.x<v.x; return u.z<v.z;} return u.y<v.y;}
int tr[200005];
int lowbit(int x){return x&-x;}
void upd(int pos,int v){
	for(;pos<=k;pos+=lowbit(pos)) tr[pos]+=v;
}
int que(int pos){
	int ans=0;
	while(pos) ans+=tr[pos],pos-=lowbit(pos);
	return ans;
}
int ans[100005],cnt[100005];
void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);
	solve(mid+1,r);
	for(int i=l;i<=r;i++) t[i]=p[i];
	for(int i=mid+1;i<=r;i++) t[i].t=1;
	sort(t+l,t+r+1,cmpy);
	for(int i=l;i<=r;i++){
		if(t[i].t==0) upd(t[i].z,t[i].cnt);
		else ans[t[i].id]+=que(t[i].z);
	}
	for(int i=l;i<=r;i++){
		if(t[i].t==0) upd(t[i].z,-t[i].cnt);
	}
}
int main(){
//	cin.tie(nullptr)->sync_with_stdio(false);
	int i;
	cin>>n>>k;
	for(i=1;i<=n;i++) cin>>t[i].x>>t[i].y>>t[i].z,t[i].id=i;
	sort(t+1,t+n+1,cmpx);
	int tot=0,c=0;
	for(i=1;i<=n;i++){
		c++;
		if(t[i].x!=t[i-1].x||t[i].y!=t[i-1].y||t[i].z!=t[i-1].z){
			p[++tot]=t[i],p[tot].cnt=c,p[tot].id=tot,c=0;
		}
	}
	solve(1,tot);
//	for(i=1;i<=n;i++) printf("%d %d %d\n",p[i].x,p[i].y,p[i].z);
//	for(i=1;i<=n;i++) cout<<ans[i]<<'\n';
	for(i=1;i<=tot;i++) cnt[ans[i]]+=p[i].cnt;
	for(i=0;i<n;i++) cout<<cnt[i]<<'\n';
	return 0;
}
2023/10/18 19:21
加载中...