限制
时间限制 1s，空间限制 512M
题目描述
Cuber QQ 有一个无向图 $G=(V,E)$，其中 $V=\{1,2,\cdots ,n\}$。 对于 $V$ 中的任意一个点 $v$， 有两个相关的点权 $f_x(v),f_y(v)$ 。
$(i,j)\in E$ 当且仅当 $|f_x(i)-f_x(j)|+|f_y(i)-f_y(j)|\le d$ 。
求 $G$ 的最大团的点数。
输入数据
输入第一行读入两个整数 $n$, $d$, 分别表示 $|V|$ 和连边的距离限制。
接下来 $n$ 行, 第 $i$ 行两个整数 $f_x (i), f_y (i)$, 表示点权。
输出数据
输出一个数表示最大团的大小。
样例
输入1
4 1
1 1
2 1
1 1
2 2输出1
3解释
点 $1, 2 3$ 之间构成了一个团。(对应的点权分别是 $(1, 1), (2, 1), (1, 1)$)
而由于点 $1$ 和点 $4$ 之间不存在边 ($|1 − 2| + |1 − 2| = 2 > 1$), 所以最大团的点数只能 是 $3$。
输入2
10 2
3 3
3 3
3 3
3 1
2 3
2 3
1 2
2 3
1 1
1 1输出2
6数据范围
这个图很明显是基于平面直角坐标系的，而曼哈顿距离小于等于 \(D\) 的点之间有边。
曼哈顿距离不好处理，果断转成切比雪夫距离。然后现在问题是如果两个点的 \(x\) 坐标之差和 \(y\) 坐标之差都小于等于 \(D\)，那么他们就有连边。
一个最大团的几何意义就变成了这些点两两之间的切比雪夫距离小于等于 \(D\)，也就是说一个边长为 \(D\) 的正方形最多可以盖住多少个的点。
考虑扫描线，我们现在扫到正方形右下角的横坐标为 \(x\)，我们要维护当正方形右下角的纵坐标为 \(y\) 时，会有多少个点。然后在最后取个最大值。
首先横坐标是一定要离散化的，然后一个点 \((x,y)\) 可以被数到，当且仅当右下角坐标在 \((x,y)\) 到 \((x+D,y+D)\) 之间。在扫描线过程中维护一颗线段树，区间修改，整体求最大值。
如果用动态开点线段树会被卡爆。所以我们把纵坐标也离散化后处理。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=1e7+5;
int n,d,l=1,tr[N<<3],x,y,p[N],ans,tag[N<<3],lsh[N<<1],q[N];
struct node{
int x,y;
bool operator<(const node&n)const{
if(x!=n.x)
return x<n.x;
return y<n.y;
}
}t[N];
void pushdown(int o,int l,int r)
{
int md=l+r>>1;
tag[o<<1]+=tag[o];
tr[o<<1]+=tag[o];
tag[o<<1|1]+=tag[o];
tr[o<<1|1]+=tag[o];
tag[o]=0;
}
void update(int o,int l,int r,int x,int y,int z)
{
if(x<=l&&r<=y)
{
tr[o]+=z;
tag[o]+=z;
return;
}
pushdown(o,l,r);
int md=l+r>>1;
if(md>=x)
update(o<<1,l,md,x,y,z);
if(md<y)
update(o<<1|1,md+1,r,x,y,z);
tr[o]=max(tr[o<<1],tr[o<<1|1]);
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
t[i].x=x-y,t[i].y=x+y;
lsh[2*i-1]=x+y,lsh[2*i]=x+y-d;
}
sort(lsh+1,lsh+2*n+1);
sort(t+1,t+n+1);
for(int i=1;i<=n;i++)
{
p[i]=lower_bound(lsh+1,lsh+2*n+1,t[i].y-d)-lsh;
q[i]=lower_bound(lsh+1,lsh+2*n+1,t[i].y)-lsh;
// printf("%d %d\n",p[i],q[i]);
}
for(int i=1;i<=n;i++)
{
while(t[l].x<t[i].x-d)
{
update(1,1,2*n,p[l],q[l],-1);
++l;
}
update(1,1,2*n,p[i],q[i],1);
ans=max(ans,tr[1]);
}
printf("%d",ans);
}