BZOJ4255：Keep Fit!

浅谈\(K-D\) \(Tree\)

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=4255

莫队加\(kd\) \(tree\)，直接用链加的方式动态删除和插入某个点，对于每个点维护子树内\(cnt\)。加上剪枝复杂度较为优越。

时间复杂度：\(O(mn)\)+剪枝

空间复杂度：\(O(n+m)\)

代码如下：

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

#define bo11 p[u].mx[0]<X1||p[u].mn[0]>X2

#define bo12 p[u].mx[1]<Y1||p[u].mn[1]>Y2

#define bo21 X1<=p[u].mn[0]&&p[u].mx[0]<=X2

#define bo22 Y1<=p[u].mn[1]&&p[u].mx[1]<=Y2

#define bo31 X1<=p[u].c[0]&&p[u].c[0]<=X2

#define bo32 Y1<=p[u].c[1]&&p[u].c[1]<=Y2

const int maxn=2e5+5,inf=2e9;

struct data {int x,y;}a[maxn];

int bel[maxn],node[maxn],ans[maxn];

int n,m,d,block,pps,res,sum,X1,X2,Y1,Y2;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct query {

	int l,r,id;

	bool operator<(const query &a)const {

		if(bel[l]!=bel[a.l])return bel[l]<bel[a.l];

		return bel[l]&1?r<a.r:r>a.r;

	}

}q[10005];

struct kd_tree {

	int root;

	int bo[maxn];

	int son[maxn][2];

	int fa[maxn],cnt[maxn];

	struct point {

		int id;

		int c[2],mn[2],mx[2];

		bool operator<(const point &a)const {

			return c[pps]<a.c[pps];

		}

	}p[maxn];

	int build(int l,int r,int cmp) {

		int mid=(l+r)>>1,u=mid;pps=cmp;

		nth_element(p+l,p+mid,p+r+1);

		node[p[u].id]=u;

		if(l<mid)fa[son[u][0]=build(l,mid-1,cmp^1)]=u;

		if(r>mid)fa[son[u][1]=build(mid+1,r,cmp^1)]=u;

		int ls=son[u][0],rs=son[u][1];

		for(int i=0;i<2;i++) {

			int mn=min(p[ls].mn[i],p[rs].mn[i]);

			p[u].mn[i]=min(p[u].c[i],mn);

			int mx=max(p[ls].mx[i],p[rs].mx[i]);

			p[u].mx[i]=max(p[u].c[i],mx);

		}

		return u;

	}

	void prepare() {

		for(int i=1;i<=n;i++) {

			p[i].c[0]=a[i].x,p[i].c[1]=a[i].y,bo[i]=0;

			p[i].id=i,son[i][0]=son[i][1]=fa[i]=cnt[i]=0;

		}

		root=build(1,n,0);

	}

	void add(int u,int v) {bo[u]+=v;while(u)cnt[u]+=v,u=fa[u];}

	void query(int u) {

		if(!cnt[u]||bo11||bo12)return;

		if(bo21&&bo22) {sum+=cnt[u];return;}

		if(bo31&&bo32)sum+=bo[u];

		if(son[u][0])query(son[u][0]);

		if(son[u][1])query(son[u][1]);

	}

}T;

void change(int pos,int v) {

	if(v==-1)T.add(node[pos],v);

	X1=a[pos].x-d,X2=a[pos].x+d;

	Y1=a[pos].y-d,Y2=a[pos].y+d;

	sum=0,T.query(T.root),res+=v*sum;

	if(v==1)T.add(node[pos],v);

}

int main() {

	int Case=0;

	T.p[0].mn[0]=T.p[0].mn[1]=inf;

	T.p[0].mx[0]=T.p[0].mx[1]=-inf;

	while(~scanf("%d%d%d",&n,&d,&m)) {

		res=0,block=sqrt(n);

		printf("Case %d:\n",++Case);

		for(int i=1;i<=n;i++) {

			bel[i]=(i-1)/block+1;

			int x=read(),y=read();

			a[i].x=x+y,a[i].y=x-y;

		}

		T.prepare();

		for(int i=1;i<=m;i++)

			q[i].l=read(),q[i].r=read(),q[i].id=i;

		sort(q+1,q+m+1);

		int l=1,r=0;

		for(int i=1;i<=m;i++) {

			while(l<q[i].l)change(l++,-1);

			while(l>q[i].l)change(--l,1);

			while(r<q[i].r)change(++r,1);

			while(r>q[i].r)change(r--,-1);

			ans[q[i].id]=res;

		}

		for(int i=1;i<=m;i++)

			printf("%d\n",ans[i]);

	}

	return 0;

}