【2023NOI模拟赛26】开开车 做题记录

有一个正 $n$ 边形，你要在上面走路。经过顶点 $i$ 和顶点 $i+1$（顶点 $n+1$ 为顶点 $1$）之间的边的代价是 $1$。

这个正 $n$ 边形上有 $n-3$ 条对角线，这些对角线把这个多边形剖成了 $n−2$ 个三角形，经过每条对角线的代价都是 $1$。

有 $q$ 次询问，每次问从顶点 $x_i$ 走到顶点 $y_i$ 的代价。

$1\le n\le 5.2\times 10^4$，$1\le q\le 2n$。

首先有一个结论，由于是三角剖分，所以一定存在某一条对角线满足它两边的顶点数都至少有 $\frac{n}{3}$ 个。

证明如图：

那么分治，每次找到两边顶点数最接近的一条对角线，以它的两个端点 $x,y$ 出发跑最短路，用 $x_i\to x\to y_i$、$x_i\to y\to y_i$ 的最短路更新第 $i$ 次询问的答案。然后删掉这条边，两边内部分治下去。

由于有那个结论，所以分治层数是 $O\left(\log_{\frac{2}{3}}n\right)$ 的，那么时间复杂度为 $O(n\log n)$。

为了避免死循环，可以在顶点数 $\le 500$ 的时候暴力。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int S=52005,BS=500;

struct ed{int x,y;};
struct que{int x,y,id;};

int n,q;
vector<int> g[S];
vector<que> qs[S];
int idx[S],dis[2][S];
int ans[S*2];

inline void bfs(int x,int st,vector<int> &V,vector<ed> &E)
{
	for(int &u:V) g[u].clear(),dis[x][u]=n+1;
	for(int i=1;i<V.size();i++) g[V[i-1]].push_back(V[i]),g[V[i]].push_back(V[i-1]);
	g[V.back()].push_back(V[0]),g[V[0]].push_back(V.back());
	for(auto &u:E) g[u.x].push_back(u.y),g[u.y].push_back(u.x);
	dis[x][st]=0;
	queue<int> q;
	q.push(st);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int &v:g[u]) if(dis[x][u]+1<dis[x][v]) dis[x][v]=dis[x][u]+1,q.push(v);
	}
}

void slove(vector<int> V,vector<ed> E,vector<que> Q)
{
	if(Q.size()==0) return;
	if(V.size()<=BS)
	{
		for(int &u:V) qs[u].clear();
		for(auto &u:Q) qs[u.x].push_back(u);
		for(int &u:V)
		{
			bfs(0,u,V,E);
			for(auto &v:qs[u]) ans[v.id]=min(ans[v.id],dis[0][v.y]);
		}
		return;
	}
	for(int i=0;i<V.size();i++) idx[V[i]]=i;
	for(auto &u:E) if(idx[u.x]>idx[u.y]) swap(u.x,u.y);
	for(auto &u:Q) if(idx[u.x]>idx[u.y]) swap(u.x,u.y);
	int mx=-1,x=-1,y=-1;
	for(auto &u:E)
	{
		int cnt=idx[u.y]-idx[u.x];
		int pre=min(cnt,(int)V.size()-cnt);
		if(pre>mx) mx=pre,x=u.x,y=u.y;
	}
	bfs(0,x,V,E),bfs(1,y,V,E);
	for(auto &u:Q)
	{
		ans[u.id]=min({ans[u.id],
			dis[0][u.x]+dis[0][u.y],
			dis[1][u.x]+dis[1][u.y]
		});
	}
	vector<int> tV;
	vector<ed> tE;
	vector<que> tQ;
	for(int i=idx[x];i<=idx[y];i++) tV.push_back(V[i]);
	for(auto &u:E) if(idx[u.x]>=idx[x]&&idx[u.y]<=idx[y]&&(u.x!=x||u.y!=y)) tE.push_back(u);
	for(auto &u:Q) if(idx[u.x]>idx[x]&&idx[u.y]<idx[y]&&(u.x!=x&&u.y!=y)) tQ.push_back(u);
	slove(tV,tE,tQ);
	for(int i=0;i<V.size();i++) idx[V[i]]=i;
	tV.clear(),tE.clear(),tQ.clear();
	for(int i=0;i<=idx[x];i++) tV.push_back(V[i]);
	for(int i=idx[y];i<V.size();i++) tV.push_back(V[i]);
	for(auto &u:E) if(((idx[u.x]<=idx[x]||idx[u.x]>=idx[y])&&(idx[u.y]<=idx[x]||idx[u.y]>=idx[y]))&&(u.x!=x||u.y!=y)) tE.push_back(u);
	for(auto &u:Q) if(((idx[u.x]<=idx[x]||idx[u.x]>=idx[y])&&(idx[u.y]<=idx[x]||idx[u.y]>=idx[y]))&&(u.x!=x&&u.y!=y)) tQ.push_back(u);
	slove(tV,tE,tQ);
}

int main()
{
	freopen("drive.in","r",stdin);
	freopen("drive.out","w",stdout);
	vector<int> V;
	vector<ed> E;
	vector<que> Q;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) V.push_back(i);
	for(int i=1;i<=n-3;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		E.push_back({x,y});
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		Q.push_back({x,y,i});
		ans[i]=n+1;
	}
	slove(V,E,Q);
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}