KD-tree求卡常
查看原帖
KD-tree求卡常
675888
__Dice__楼主2024/3/26 21:45

RT

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define rep(i,n) for(int i=1;i<=n;++i)
#define lop(i,n) for(int i=n;i;--i)
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=2e5+7,inf=1e9;
struct seg{
	#define lson l,m,ls[rt]
	#define rson m+1,r,rs[rt]
	static const int uii=1e7;
	int c[uii],tot=0,ls[uii],rs[uii],g=1;
	void clear(){
		rep(i,tot)ls[i]=rs[i]=c[i]=0;
		tot=1;
	}
	seg(){
		clear();
	}
	void pushup(int rt){
		c[rt]=c[ls[rt]]+c[rs[rt]];
	}
	void update(int l,int r,int&rt,int pos){
		if(!rt)rt=++tot;
		if(l==r)return c[rt]++,void();
		int m=(l+r)>>1;
		if(pos<=m)update(lson,pos);
		else update(rson,pos);
		pushup(rt);
	}
	int que(int l,int r,int rt,int L,int R){
		if(!rt)return 0;
		if(L<=l&&R>=r)return c[rt];
		int m=(l+r)>>1,s=0;
		if(L<=m)s=que(lson,L,R);
		if(R>m)s+=que(rson,L,R);
		return s;
	}
	int que(int l,int r){
		if(l>r)return 0;
		return que(1,inf,g,l,r);
	}
	void upd(int pos){
		update(1,inf,g,pos);
	}
}tr;
struct pt{
	int x,y,v,id;
}s[N],tmp[N];
bool cmpx(pt x,pt y){
	return x.x==y.x?x.y<y.y:x.x<y.x;
}
bool cmpy(pt x,pt y){
	return x.y==y.y?x.x<y.x:x.y<y.y;
}
struct KD{
	int D[N],U[N],L[N],R[N],add[N],ls[N],rs[N];
	void pushup(int rt){
		L[rt]=R[rt]=s[rt].x;
		U[rt]=D[rt]=s[rt].y;
		if(ls[rt]){
			L[rt]=min(L[rt],L[ls[rt]]);R[rt]=max(R[rt],R[ls[rt]]);
			U[rt]=min(U[rt],U[ls[rt]]);D[rt]=max(D[rt],D[ls[rt]]);
		}
		if(rs[rt]){
			L[rt]=min(L[rt],L[rs[rt]]);R[rt]=max(R[rt],R[rs[rt]]);
			U[rt]=min(U[rt],U[rs[rt]]);D[rt]=max(D[rt],D[rs[rt]]);
		}
	}
	int build(int l,int r,bool ff){
		if(l>r)return 0;
		int mid=(l+r)>>1;
		nth_element(s+l,s+mid,s+r+1,ff?cmpx:cmpy);
		s[mid].v=add[mid]=0;
		ls[mid]=build(l,mid-1,ff^1);
		rs[mid]=build(mid+1,r,ff^1);
		pushup(mid);
		return mid;
	}
	void addd(int rt,int x){
		s[rt].v+=x;add[rt]+=x;
	}
	void pd(int rt){
		if(add[rt]){
			if(ls[rt])addd(ls[rt],add[rt]);
			if(rs[rt])addd(rs[rt],add[rt]);
			add[rt]=0;
		}
	}
	void ad(int l,int r,int ql,int qr,int qu,int qd,int val=1){
		if(ql>qr||qu>qd)return;
		if(l>r)return;
		int mid=(l+r)>>1;
		if(L[mid]>qr||R[mid]<ql||U[mid]>qd||D[mid]<qu)return;
		if(ql<=L[mid]&&qr>=R[mid]&&qu<=U[mid]&&qd>=D[mid])return addd(mid,val),void();
		int x=s[mid].x,y=s[mid].y;
		if(ql<=x&&qr>=x&&qu<=y&&qd>=y)s[mid].v+=val/*,printf("(%lld,%lld):(%lld,%lld):s[%lld]=%lld\n",l,r,ql,qr,s[mid].x,s[mid].v)*/;
		pd(mid);
		if(ls[mid])ad(l,mid-1,ql,qr,qu,qd,val);
		if(rs[mid])ad(mid+1,r,ql,qr,qu,qd,val);
	}
	int que(int l,int r,int x,int y){
		if(l>r)return 0;
		int mid=(l+r)>>1;
		if(L[mid]>x||R[mid]<x||U[mid]>y||D[mid]<y)return 0;
		if(s[mid].x==x&&s[mid].y==y)return s[mid].v;
		int ss=0;pd(mid);
		if(ls[mid])ss=que(l,mid-1,x,y);
		if(rs[mid])ss=max(ss,que(mid+1,r,x,y));
		return ss;
	}
}kd;
int ans[N],n;
struct jf{
	int op,id;
};
map<int,vector<int>>ad;
map<int,vector<jf>>que;
#define pb push_back
main(){
	cin>>n;
	rep(i,n){
		tmp[i].id=i;
		scanf("%d%d%d",&tmp[i].x,&tmp[i].y,&tmp[i].v);
	}
	sort(tmp+1,tmp+1+n,cmpx);
	tr.clear();
	for(int i=1,uy;i<=n;){
		uy=i;
		while(tmp[uy].x==tmp[i].x)tr.upd(tmp[uy].y),++uy;
		int tm;
		for(;i<uy;++i)
		ans[tmp[i].id]+=(tm=(tr.que(tmp[i].x+tmp[i].v,inf)-1)),
		ans[tmp[i].id]-=(tm=(tr.que(tmp[i].y,inf)-1));
	}
	sort(tmp+1,tmp+1+n,cmpy);
	tr.clear();
	for(int i=n,uy;i;){
		uy=i;
		while(tmp[uy].y==tmp[i].y)tr.upd(tmp[uy].x),--uy;
		for(;i>uy;--i)
		ans[tmp[i].id]+=tr.que(1,tmp[i].y-tmp[i].v)-1;
	}
	rep(i,n)s[i].x=tmp[i].x,s[i].y=tmp[i].y;
	kd.build(1,n,0);
	rep(i,n)que[tmp[i].v-1].pb({-1,i}),que[tmp[i].y-tmp[i].x].pb({1,i}),
	ad[tmp[i].y-tmp[i].x].pb(i);
	for(auto V:que){
		int ti=V.first;auto vv=V.second;
		for(auto i:ad[ti])kd.ad(1,n,1,tmp[i].x-1,tmp[i].y+1,inf);
		for(auto VV:vv){
			int i=VV.id,op=VV.op;
			int jkl;
			ans[tmp[i].id]+=op*(jkl=kd.que(1,n,tmp[i].x,tmp[i].y));
		}
	}
	rep(i,n)printf("%d\n",ans[i]);
	return 0;
}
2024/3/26 21:45
加载中...