【题解】CF1184C2

一个半径为 rr 的圆中所有点都对这个圆心有 11 的贡献;同样地,一个点对以这个点为圆心,半径为 rr 的圆中所有的圆心都有 11 的贡献。

考虑曼哈顿距离转切比雪夫距离,这样之后一个半径为 rr 的“圆”就变成了一个边长 2r+12r+1 的正方形。

把点按横坐标升序排序,枚举圆心的横坐标,对纵坐标建线段树即可动态维护这时答案的最大值。

// 2020.09.29
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define fi first
#define se second
inline int read(){
    int x=0,f=1;
    char ch;
    while(ch<'0'||ch>'9')  {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}

const int MAXN=300005;
const int MAX=2e6+5000;
int n,rad;
int ans=1;
pair<int,int> a[MAXN];

struct Segment_Tree{
	const int INF=0x3f3f3f3f;
	struct node{
		int l,r;
		int add,mx;
	}st[MAX*8];
	
	void build(int p,int l,int r){
		st[p].l=l;st[p].r=r;
		if (l==r){
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		st[p].mx=max(st[p<<1].mx,st[p<<1|1].mx);
	}

	void spread(int p){
		st[p<<1].add+=st[p].add;
		st[p<<1|1].add+=st[p].add;
		st[p<<1].mx+=st[p].add;
		st[p<<1|1].mx+=st[p].add;
		st[p].add=0;
	}

	void change(int p,int l,int r,int c){
		if (l<=st[p].l&&st[p].r<=r){
			st[p].add+=c;
			st[p].mx+=c;
			return;
		}
		spread(p);
		int mid=st[p].l+st[p].r>>1;
		if (l<=mid) change(p<<1,l,r,c);
		if (r>mid) change(p<<1|1,l,r,c);
		st[p].mx=max(st[p<<1].mx,st[p<<1|1].mx);
	}

	int query_max(int p,int l,int r){
		if (l<=st[p].l && st[p].r<=r)
			return st[p].mx;
		spread(p);
		int mid=st[p].l+st[p].r>>1,ans=-INF;
		if (l<=mid) ans=query_max(p<<1,l,r);
		if (r>mid) ans=max(ans,query_max(p<<1|1,l,r));
		return ans;
	}
}seg;

signed main()

{
	n=read();rad=read();
	int mx=0;
	for (int i=1;i<=n;i++){
		int x=read(),y=read();
		int tmp=x;
		a[i].fi=x+y+MAX;
		a[i].se=x-y+MAX;
		mx=max(mx,a[i].fi);
	}

	sort(a+1,a+1+n);

	seg.build(1,1,MAX*2);
	int l=1,r=1;

	for (int i=a[1].fi;i<=mx;i++){
		while (r<=n && a[r].fi<=i+rad){
			seg.change(1,a[r].se-rad,a[r].se+rad,1);
			r++;
		}
		while (l<=n && a[l].fi<i-rad){
			seg.change(1,a[l].se-rad,a[l].se+rad,-1);
			l++;
		}

		ans=max(ans,seg.query_max(1,1,MAX*2));
	}

	cout<<ans<<endl;
	return 0;
}

小声bb:值域开到 10910^9 的话其实也可做。

考虑对于一个横坐标为 xx 的点,它对线段树做的修改只有可能在 xr,x+r+1x-r,x+r+1 这两个地方发生。于是我们只需要枚举这些点,原方法中“枚举圆心横坐标”这一操作的复杂度降至 2n2n。线段树加上动态开点,总复杂度即可优化到 O(nlogW)\mathcal{O(n \log W)},其中 W\mathcal{W} 为值域。