目录
显示
题目链接
题解
一道非常棒的题。
Subtask 2
我们考虑建立图论模型，套最短路算法来做。
对于每个点，分别考虑这个点左边和右边的所有点，向它能到达的左边/右边的第一个点分别连一条边。
为啥是第一个点呢？目的是为了减少重复的边（\(a \to b \to c\) 这条路径只用连 \(a \to b\) 和 \(b \to c\) 的边，不用连 \(a \to c\) 的边了）。
这样连边后的图最多有 \(O(N)\) 条边，在新图上跑最短路即可。
时间复杂度 \(O(QN \log N)\)，期望得分：20 pts。
Subtask 4
我们接下来从区间的角度来考虑这道题。
我们之前已经求出，在花费为 \(1\) 时，从 \(i\) 号节点出发，最左可以到达 \(l_i\) 号节点，最右可以到达 \(r_i\) 号节点。
那么在花费为 \(k\) 的时候，从 \(i\) 号节点最左和最右可以到达的点怎么求呢？
容易发现这个可以倍增来算。
现在我们把这些区间展开成一棵树：如果区间 \(a\) 完全包含了区间 \(b\)，且区间 \(a\) 代表了从 \(i\) 出发跳 \(k\) 次覆盖的区间，区间 \(b\) 代表了从 \(i\) 出发跳 \(k-1\) 次覆盖的区间，那么我们将 \(b\) 挂在 \(a\) 下面。
现在来转化问题：我们现在让 \([A,A]\) 和 \([B,B]\) 两个点向上跳，直到它们的父节点相同为止（也就是说这两个区间紧挨着，别忘了起点和终点不算入答案）。这时候我们跳的次数就是答案。
时间复杂度 \(O(Q \log N)\)，期望得分：100 pts。
#include <iostream>
#include <stack>
using namespace std;
int l[100005],f[100005][25],g[100005][25];
stack<int> s;
int main()
{
ios::sync_with_stdio(false);
int n,k,q;
cin>>n>>k>>q;
for(int i=1;i<=n;i++)
cin>>l[i];
for(int i=1;i<=n;i++)
{
while(!s.empty()&&l[s.top()]<l[i])
s.pop();
if(!s.empty())f[i][0]=s.top();
else f[i][0]=i;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=n;i;i--)
{
while(!s.empty()&&l[s.top()]<l[i])
s.pop();
if(!s.empty())g[i][0]=s.top();
else g[i][0]=i;
s.push(i);
}
for(int k=1;k<=17;k++)
for(int i=1;i<=n;i++)
{
f[i][k]=min(f[f[i][k-1]][k-1],f[g[i][k-1]][k-1]);
g[i][k]=max(g[f[i][k-1]][k-1],g[g[i][k-1]][k-1]);
}
while(q--)
{
int a,b,l,r;
cin>>a>>b;
if(a>b)swap(a,b);
int ans=0;
l=r=a;
for(int k=17;k>=0;k--)
{
int u=min(f[l][k],f[r][k]),v=max(g[l][k],g[r][k]);
if(v<b)
{
l=u,r=v;
ans+=(1<<k);
}
}
a=r;
l=r=b;
for(int k=17;k>=0;k--)
{
int u=min(f[l][k],f[r][k]),v=max(g[l][k],g[r][k]);
if(u>a)
{
l=u,r=v;
ans+=(1<<k);
}
}
cout<<ans<<endl;
}
return 0;
}