「BZOJ 4449」[Neerc2015]Distance on Triangulation

发表于

给定一个凸 nn 边形，以及它的三角剖分。再给定 qq 个询问，每个询问是一对凸多边行上的顶点 (a,b)(a,b) ，问点 aa 最少经过多少条边(可以是多边形上的边，也可以是剖分上的边)可以到达点 bb 。

Constraints

n≤50000n \leq 50000 ，q≤100000q \leq 100000

Solution

运用分治的思想，每一次选择一条剖分边，使得凸多边形分成尽量平均的两部分。使用 bfs 得出该条边的两个端点到各个顶点的最短路，对所有的询问在两个端点处进行拼凑并更新答案。然后对两部分的信息分别划开，进行下一层的分治。

（每次分治完，点数会比原来多 22 ，所以空间要开三倍。）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int n,m,cnt,x,y,t,tmp;
int first[N],ans[N],id[N];
int qq[N],disx[N],disy[N],q1[N],q2[N];
bool ok[N];
struct node{int x,y,id;}l[N],q[N],h1[N],h2[N];
struct edge{int to,next;}e[N<<1];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
int find(int l,int r,int x){return lower_bound(id+l,id+r+1,x)-id;}
void bfs(int S,int pl,int pr,int *dis)
{
    int head=0,tail=0;
    for(int i=pl;i<=pr;i++)dis[id[i]]=inf;
    qq[tail++]=S;dis[S]=0;
    while(head!=tail)
    {
        int u=qq[head++];
        for(int i=first[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(!ok[to])continue;
            if(dis[to]==inf)dis[to]=dis[u]+1,qq[tail++]=to;
        }
    }   
}
void work(int dl,int dr,int pl,int pr,int ql,int qr)
{
    if(dl>dr||pl>pr||ql>qr)return;
    int mn=inf,mnid=0;
    for(int i=dl;i<=dr;i++)
    {
        x=find(pl,pr,l[i].x);y=find(pl,pr,l[i].y);
        if(x>y)swap(x,y);
        tmp=max(y-x,x-y+pr-pl+1);
        if(tmp<mn)mn=tmp,mnid=i;
    }
    for(int i=pl;i<=pr;i++)ok[id[i]]=true;
    bfs(l[mnid].x,pl,pr,disx);
    bfs(l[mnid].y,pl,pr,disy);
    for(int i=pl;i<=pr;i++)ok[id[i]]=false;
    int t1=0,t2=0,t3=0,t4=0,t5=0,t6=0;
    for(int i=ql;i<=qr;i++)
    {
        x=q[i].x;y=q[i].y;t=q[i].id;
        if(x==l[mnid].x&&y==l[mnid].y){ans[t]=1;continue;}
        ans[t]=min(ans[t],disx[x]+disx[y]);
        ans[t]=min(ans[t],disy[x]+disy[y]);
        ans[t]=min(ans[t],disx[x]+disy[y]+1);
        ans[t]=min(ans[t],disy[x]+disx[y]+1);
        if(q[i].x>l[mnid].x&&q[i].y<l[mnid].y)h1[++t1]=q[i];
        else if((q[i].x<l[mnid].x||q[i].x>l[mnid].y)&&
        (q[i].y<l[mnid].x||q[i].y>l[mnid].y))h2[++t2]=q[i];
    }
    for(int i=1;i<=t1;i++)q[ql+i-1]=h1[i];
    for(int i=1;i<=t2;i++)q[ql+t1+i-1]=h2[i];
    for(int i=pl;i<=pr;i++)
    {
        if(id[i]>=l[mnid].x&&id[i]<=l[mnid].y)q1[++t3]=id[i];
        if(id[i]<=l[mnid].x||id[i]>=l[mnid].y)q2[++t4]=id[i];
    }
    for(int i=1;i<=t3;i++)id[pl+i-1]=q1[i];
    for(int i=1;i<=t4;i++)id[pl+t3+i-1]=q2[i];
    for(int i=dl;i<=dr;i++)
    {
        if(i==mnid)continue;
        if(l[i].x>=l[mnid].x&&l[i].y<=l[mnid].y)h1[++t5]=l[i];
        else h2[++t6]=l[i];
    }
    for(int i=1;i<=t5;i++)l[dl+i-1]=h1[i];
    for(int i=1;i<=t6;i++)l[dl+t5+i-1]=h2[i];
    work(dl+t5,dl+t5+t6-1,pl+t3,pl+t3+t4-1,ql+t1,ql+t1+t2-1);
    work(dl,dl+t5-1,pl,pl+t3-1,ql,ql+t1-1); 
}
int main()
{
    n=read();
    for(int i=1;i<=n-3;i++)
    {
        l[i].x=read();l[i].y=read();
        ins(l[i].x,l[i].y);ins(l[i].y,l[i].x);
        if(l[i].x>l[i].y)swap(l[i].x,l[i].y);
    }
    for(int i=1;i<n;i++)ins(i,i+1),ins(i+1,i);
    ins(1,n);ins(n,1);
    m=read();
    for(int i=1;i<=m;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);
        ans[i]=min(q[i].y-q[i].x,q[i].x-q[i].y+n);
    }
    for(int i=1;i<=n;i++)id[i]=i;
    work(1,n-3,1,n,1,m);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}