Description
Solution
题目要求的是曼达顿距离，对于每个点(x,y)，我们把它变为(x-y,x+y)，就可以转换成求切比雪夫距离了。
证明如下:$max(\left | (x_{p}-y_{p})-(x_{q}-y_{q}) \right |,\left | (x_{p}+y_{p})-(x_{q}+y_{q}) \right |)=max(\left | x_{p}-x_{q}\pm(y_{p}-y_{q}) \right | )=\left | x_{p}-x_{q} \right |+\left | y_{p}-y_{q} \right |$
设点a，b距离为d。
针对每个点i，讨论y值比y[i]恰好小d，且x与x[i]的差比d小的点的个数(记为cnt[i])并把这些点放到并查集内。（记得判重）
交换x,y值再重复一次上述步骤。
最后就同一个联通块算一下cnt的和就ok。
Code
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; typedef long long ll; vector<pair<ll,int> >v; int n,a,b,x,y; ll d; struct P{ll x,y,id; friend bool operator <(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}}p[100010]; int dis(P a,P b){return abs(a.x-b.x)+abs(a.y-b.y);} int fa[100010];ll sz[100010]; int find_f(int x){return fa[x]==x?x:fa[x]=find_f(fa[x]);} int cnt[100010]; void solve(int now) { vector<pair<ll,int> >::iterator _last,it; v.clear(); int pre=1;bool _is=0; for (int i=1;i<=n;i++) { if (p[i].x!=p[i-1].x) v.clear(),_is=1; while (p[i].x-p[pre].x>d&&pre<=n) pre++; while (p[i].x-p[pre].x==d&&pre<=n) v.push_back(make_pair(p[pre].y,p[pre].id)),++pre; it=lower_bound(v.begin(),v.end(),make_pair(p[i].y-d+now,0)); if (_is){_is=0;_last=v.begin();} _last=max(_last,it); if (it==v.end()||it->first >p[i].y+d-now) continue; for(;_last!=v.end()&&_last->first<=p[i].y+d-now;_last++) { x=find_f(_last->second);y=find_f(p[i].id); if (x!=y) fa[x]=y; } cnt[p[i].id]+=(_last-it); if (_last!=it) _last--; } } int main() { scanf("%d%d%d",&n,&a,&b); for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); d=dis(p[a],p[b]); for (int i=1;i<=n;i++) {fa[i]=i;x=p[i].x;y=p[i].y;p[i].x=x-y;p[i].y=x+y;p[i].id=i;} sort(p+1,p+n+1); solve(0); for (int i=1;i<=n;i++) swap(p[i].x,p[i].y); sort(p+1,p+n+1); solve(1); for (int i=1;i<=n;i++) sz[find_f(i)]+=cnt[i]; cout<<sz[find_f(a)]; }