JOISC2017F 鉄道旅行 (Railway Trip) 做题记录

给定长 $n$ 的序列 $a_i$，满足 $a_1=a_n=\max\{a_i\}$。

构建一个 $n$ 个点的无向图 $G$ 如下：

• $\forall 1\le i<j\le n$，若存在某个正整数 $k$ 满足 $a_i,a_j\ge k$ 且 $\forall i<p<j$ 都有 $a_p<k$，则 $G$ 中存在边 $(i,j)$；

$q$ 次询问，每次询问点 $x_i$ 和 $y_i$ 之间的最短路长度减一。

$1\le n,q\le 10^5$，$1\le a_i\le n$。

不妨称满足 $a_i,a_j\ge k$ 且 $\forall i<p<j$ 都有 $a_p<k$ 的边 $(i,j)$ 为 $k-\text{边}$。

不难发现若把边 $(x,y)$ 看作区间 $[x,y-1]$，则：

• 任意两个区间要么包含要么相离；
• 对于同一个 $k$，所有 $k-\text{边}$ 对应的区间的并为 $[1,n-1]$（整个序列）；
• 对于某条 $k-边$ $(l,r)$，$\forall k'< k$，所有满足 $l\le x\le y\le r$ 的 $k'-边$ $(x,y)$ 对应的区间的并为 $[l,r-1]$；

那么这些边形成了类似树的结构：把每一条边看作一个点，则对于每一条 $k-\text{边}$ $(x,y)$，所有端点在 $[x,y]$ 内的 $(k-1)-\text{边}$ 都是它的儿子。

那么最短路的形态肯定是不断往父亲走，走到 $\text{lca}$ 后再往儿子走。

也就是说，设路径序列为 $p$，则：

• 存在一个分界点 $l$，满足 $\forall i< l$，$a_{p_i}\le a_{p_{i+1}}$ 且 $\forall i>l$，$a_{p_{i-1}}\ge a_{p_i}$，即路径上的 $a_i$ 先增再减；
• $\forall p_i<j<p_{i+1}$，都有 $a_j\le \min(a_{p_i},a_{p_{i+1}})$，否则把 $j$ 加入 $p$ 肯定不劣；

那么考虑倍增，不妨设 $lb_{i,j}$ 和 $rb_{i,j}$ 分别表示 $p$ 长度为 $2^j$ 且 $p_1=i$ 时 $p_j$ 可能的最小值和最大值，显然 $\forall lb_{i,j}<k<rb_{i,j}$ 都有 $a_k<\min(a_{lb_{i,j}},a_{rb_{i,j}})$。

那么根据之前的结论，有：

$lb_{i,j}=\min(lb_{lb_{i,j-1},j-1},lb_{rb_{i,j-1},j-1})\\ rb_{i,j}=\max(rb_{lb_{i,j-1},j-1},rb_{rb_{i,j-1},j-1})\\$

而 $lb_{i,0}$ 和 $rb_{i,0}$ 分别为 $i$ 左边和右边第一个 $a_j>a_i$ 的 $j$。

不妨令询问的 $x_i\le y_i$，则每次询问：

1. 从 $x_i$ 开始在 $rb<y_i$ 的情况下不断跳 $rb$，设最后跳到了 $r$；
2. 从 $y_i$ 开始在 $lb>r$ 的情况下不断跳 $lb$；

时间复杂度 $O((n+q)\log n)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005,BS=25;

int n,k,q,a[S];
int top,sta[S];
int lb[S][BS],rb[S][BS];

int main()
{
	scanf("%d%d%d",&n,&k,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	top=0;
	for(int i=1;i<=n;i++)
	{
		while(top>0&&a[sta[top]]<a[i]) top--;
		lb[i][0]=top==0?i:sta[top];
		sta[++top]=i;
	}
	top=0;
	for(int i=n;i>=1;i--)
	{
		while(top>0&&a[sta[top]]<a[i]) top--;
		rb[i][0]=top==0?i:sta[top];
		sta[++top]=i;
	}
	for(int j=1;j<=BS-3;j++)
	{
		for(int i=1;i<=n;i++)
		{
			int l=lb[i][j-1],r=rb[i][j-1];
			lb[i][j]=min(lb[l][j-1],lb[r][j-1]);
			rb[i][j]=max(rb[l][j-1],rb[r][j-1]);
		}
	}
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		int ans=0;
		int l=x,r=x;
		for(int i=BS-3;i>=0;i--)
		{
			if(max(rb[l][i],rb[r][i])<y)
			{
				ans+=1<<i;
				int tl=l,tr=r;
				l=min(lb[tl][i],lb[tr][i]);
				r=max(rb[tl][i],rb[tr][i]);
			}
		}
		int u=r;
		l=y,r=y;
		for(int i=BS-3;i>=0;i--)
		{
			if(min(lb[l][i],lb[r][i])>u)
			{
				ans+=1<<i;
				int tl=l,tr=r;
				l=min(lb[tl][i],lb[tr][i]);
				r=max(rb[tl][i],rb[tr][i]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}