【AtCoder Regular Contest 065 E】Manhattan Compass | Mrsrz's blog

曼哈顿距离转切比雪夫距离，平衡树，STL。

题目大意：

给定平面上 $n$ 个点，当前有两个指针分别指向 $p,q$（$p,q$ 和 $q,p$ 没有区别）。

令 $d(p,q)$ 表示 $p$ 和 $q$ 的曼哈顿距离。

若存在 $p,q,r$ 满足 $d(p,q)=d(p,q)$，则可以将指针从 $p,q$ 变为 $p,r$。

问有多少对 $i,j$ 能被指针指到（$i\lt j$）。

题解：

将原来的坐标 $(x,y)$ 变为 $(x+y,x-y)$，这样两点的曼哈顿距离就变为切比雪夫距离。

对于一个点 $(x,y)$，和它切比雪夫距离为 $k$ 的点分布在 $(x-k,y-k..y+k)$，$(x+k,y-k..y+k)$，$(x-k..x+k,y-k)$，$(x+k,y-k..y+k)$ 上，也就是四条线段。

我们先考虑求出所有能到达的结点。用平衡树存储每个横坐标、纵坐标上的所有点，每次扩展一个点，就在平衡树上找到它能到达的点，插入队列，然后在平衡树中删除这些结点。这样保证每个结点只会被删除、扩展到一次，复杂度为 $O(n\log n)$。

再考虑求点对数量。为了防止算重，我们对一个点只考虑上面、右边的两条线段上的结点。这些可以通过一开始在平衡树上查询 rank 得到。

由于坐标较大，而且需要支持查询 rank，所以我们可以使用 map 离散坐标，map 里套 pbds 的 tree 以支持查询 rank。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<map>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;using namespace std;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>TR;
const int N=1e5+5;
int n,a,b,X[N],Y[N],k,cnt[N];
long long t;
bool vis[N];
map<int,TR>R,C;
queue<int>q;
int count(TR&st,int l,int r){
    return(int)st.order_of_key(make_pair(r+1,0))-(int)st.order_of_key(make_pair(l,0));
}
void solve(TR&st,int l,int r){
    auto L=st.lower_bound(make_pair(l,0)),R=st.lower_bound(make_pair(r+1,0));
    vector<TR::iterator>vec;
    for(auto i=L;i!=R;++i){
        if(!vis[i->second])vis[i->second]=1,q.push(i->second);
        vec.push_back(i);
    }
    for(auto i:vec)st.erase(i);
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        X[i]=x+y-0*1000000000,Y[i]=x-y;
        R[X[i]].insert(make_pair(Y[i],i)),C[Y[i]].insert(make_pair(X[i],i));
    }
    k=max(abs(X[a]-X[b]),abs(Y[a]-Y[b]));
    for(int i=1;i<=n;++i)
    cnt[i]=count(R[X[i]-k],Y[i]-k,Y[i]+k-1)+count(C[Y[i]+k],X[i]-k,X[i]+k-1);
    q.push(a),q.push(b);
    vis[a]=vis[b]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        t+=cnt[u];
        solve(R[X[u]-k],Y[u]-k,Y[u]+k);
        solve(R[X[u]+k],Y[u]-k,Y[u]+k);
        solve(C[Y[u]-k],X[u]-k,X[u]+k);
        solve(C[Y[u]+k],X[u]-k,X[u]+k);
    }
    printf("%lld\n",t);
    return 0;
}