题目描述

给定一个正 n 边形及其三角剖分, 共 2n − 3 条边 (n 条多边形的边和 n − 3 条对角线), 每条边的长度为 1.
共 q 次询问, 每次询问给定两个点, 求它们的最短距离.

数据范围

1 ≤ n ≤ 52000, 1 ≤ q ≤ 2n.

解题思路

划分一刀，相当于将原多边形分成了两个新的多边形，这不由得让人想到分治。于是我们把询问，边和点拿来一起分治。

每次在当前的边中暴力找到将多边形的点划分得最均匀的一条边，假设边的两端的点编号是 x,y，则划分出来的两个区间中有一个的点编号都大于等于 x 小于等于 y，这就是我们分治时的划分方法。然后很显然，把这个区域的询问，边，点划到一边，那个区域的划到另一边，分别分治。而跨越两个区域的询问，我们可以使用 bfs，找出当前每一个点到划分线上两个点的距离，处理这些询问。

复杂度分析：常数巨大的 $O(nlogn)$

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
#define RI register int
const int N=102005,inf=0x3f3f3f3f;
int n,Q,tot,nico;
int h[N],ne[N],to[N],bh[N],pos[N],b1[N],b2[N];
int dis[2][N],vis[N],canvis[N],que[N],ans[N];
struct query{int x,y,id;}q[N],q1[N],q2[N],q3[N],e[N];

void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void bfs(int o,int st,int bl,int br) {
    ++nico;int he=1,ta=1;
    for(RI i=bl;i<=br;++i) canvis[bh[i]]=nico,vis[bh[i]]=0;
    dis[o][st]=0,que[1]=st,vis[st]=1;
    while(he<=ta) {
        int x=que[he];++he;
        for(RI i=h[x];i;i=ne[i])
            if(canvis[to[i]]==nico&&!vis[to[i]])
                vis[to[i]]=1,dis[o][to[i]]=dis[o][x]+1,que[++ta]=to[i];
    }
}
void work(int bl,int br,int ql,int qr,int el,int er) {//点区间，询问区间，边区间
  if(ql>qr) return;
    if(el>er) return;
    for(RI i=bl,j=1;i<=br;++i,++j) pos[bh[i]]=j;//离散
    int bj=0,mx=inf;
    for(RI i=el;i<=er;++i) {//寻找最优划分边
        int kl=pos[e[i].y]-pos[e[i].x]+1;
        if(max(kl,br-bl+3-kl)<mx) mx=max(kl,br-bl+3-kl),bj=i;
    }
    int a=e[bj].x,b=e[bj].y,t1=0,t2=0,t3=0;
    for(RI i=ql;i<=qr;++i) {//划分询问
        int kx=q[i].x>a&&q[i].x<b,ky=q[i].y>a&&q[i].y<b;
        if(kx!=ky||a==q[i].x||b==q[i].x||a==q[i].y||b==q[i].y) q3[++t3]=q[i];
        else if(!kx) q1[++t1]=q[i];
        else q2[++t2]=q[i];
    }
    bfs(0,a,bl,br),bfs(1,b,bl,br);
    for(RI i=1;i<=t3;++i)//计算跨两边的询问的答案
        ans[q3[i].id]=min(dis[0][q3[i].x]+dis[0][q3[i].y],dis[1][q3[i].x]+dis[1][q3[i].y]);
    //以下是分治的划分过程
    for(RI i=1;i<=t1;++i) q[ql+i-1]=q1[i];
    for(RI i=1;i<=t2;++i) q[ql+i+t1-1]=q2[i];
    int bt1=0,bt2=0,kb1=bh[br+1],kb2=bh[br+2];
    //kb1,kb2: 划分线上的两个点会覆盖掉 bh[br+1] 和 bh[br+2]，要回溯
    for(RI i=bl;i<=br;++i) {
        if(bh[i]==a||bh[i]==b) b1[++bt1]=bh[i],b2[++bt2]=bh[i];
        else if(bh[i]<a||bh[i]>b) b1[++bt1]=bh[i];
        else b2[++bt2]=bh[i];
    }
    for(RI i=1;i<=bt1;++i) bh[bl+i-1]=b1[i];
    for(RI i=1;i<=bt2;++i) bh[bl+bt1+i-1]=b2[i];
    int et1=0,et2=0;
    for(RI i=el;i<=er;++i) {
        if(i==bj) continue;
        if(e[i].x<a||e[i].x>=b||(e[i].x==a&&e[i].y>b)) q1[++et1]=e[i];
        else q2[++et2]=e[i];
    }
    for(RI i=1;i<=et1;++i) e[el+i-1]=q1[i];
    for(RI i=1;i<=et2;++i) e[el+et1+i-1]=q2[i];
    work(bl,bl+bt1-1,ql,ql+t1-1,el,el+et1-1);
    work(bl+bt1,bl+bt1+bt2-1,ql+t1,ql+t1+t2-1,el+et1,el+et1+et2-1);
    bh[br+1]=kb1,bh[br+2]=kb2;
}
int main()
{
    freopen("bsh.in","r",stdin);
    freopen("bsh.out","w",stdout);
    n=read();
    for(RI i=1;i<=n-3;++i) {
        e[i].x=read(),e[i].y=read();
        if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
        add(e[i].x,e[i].y),add(e[i].y,e[i].x);
    }
    Q=read();
    for(RI i=1;i<=Q;++i) {
        q[i].x=read(),q[i].y=read(),q[i].id=i;
        if(q[i].x>q[i].y) swap(q[i].x,q[i].y);
    }
    for(RI i=1;i<n;++i) add(i,i+1),add(i+1,i);
    add(1,n),add(n,1);
    for(RI i=1;i<=n;++i) bh[i]=i;
    work(1,n,1,Q,1,n-3);
    for(RI i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}