AT_joisc2017_f Railway Trip (倍增)
chenwenmo
·
·
题解
题意
某条铁路线（非环线）有 N 站，依次编号为 1\ldots N。这条线路上跑着 K 类列车，编号为 1\ldots K。每种列车都是双向运行的。
这条铁路线上的每个车站都有个旅客流量，旅客流量是一个 \le K 的正整数。车站 i(1\le i\le N) 的旅客流量为 L_i，L_1=L_N=K。
第 j 类列车 (1\le j\le N) 在且只在旅客流量 \ge j 的车站停车。
现有 Q 名旅客，依次编号为 1\ldots Q，旅客 k(1\le k\le Q) 的起点是车站 A_k，终点是 B_k (1\le A_k, B_k\le N)。假设这些旅客只能靠这条铁路线移动。
对于每个旅客，求这名旅客的途中至少要停几次站（不含该旅客的起终点站）。保证同一名旅客的起点与终点不同。允许走回头路。
思路
我一开始的思路是将每个站和它左边和右边第一个 \ge 它的站点连边，但是我不知道怎么快速求最短路，一看题解要用三角剖分，就放弃了（本蒟蒻不会。
对于起点 x 和终点 y，要从起点跳到终点，经过的点（也就是要停的站），一定是一个上凸的结构，p_1\le p_2\le ...\ p_i\ge p_{i+1}\ge p_{i+2}\ ...，证明很容易，因为如果中间有一段是下凸，也就是往下跳，p_1\ge p_2\le p_3，那还不如直接从 p_1 跳到 p_3。
因此路径上必有一个点，是起点和终点路径之间最高的点。
那么我们要做的就是求出起点到中间最高点的最短距离，以及终点到最高点的距离只有 1 的最短距离，加起来就是答案了。
考虑倍增优化，设 l(j,i) 表示从 i 点跳 2^j 步最左跳到哪，r(j,i) 表示最右跳到哪，因为要跳最远，那么每次肯定往流量大于等于它的站点跳，证明和上面类似。
转移方程：l(j,i)=\min(l(j-1,l(j-1,i)),l(j-1,r(j-1,i)))，r 同理。
### 代码
```cpp
const int N = 1e5 + 10, L = 30;
int n, k, q, a[N], l[L][N], r[L][N];
stack <int> s;
ll ans;
void Solve(){
cin >> n >> k >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
while(!s.empty() && a[s.top()] <= a[i]){
r[0][s.top()] = i;
if(!l[0][i] && a[s.top()] == a[i]) l[0][i] = s.top();
s.pop();
}
if(!s.empty() && !l[0][i] && a[s.top()] > a[i]) l[0][i] = s.top();
s.push(i);
}
l[0][1] = 1;
r[0][n] = n;
for(int i = 1; i <= 20; i++){
for(int j = 1; j <= n; j++){
l[i][j] = min(l[i - 1][l[i - 1][j]], l[i - 1][r[i - 1][j]]);
r[i][j] = max(r[i - 1][r[i - 1][j]], r[i - 1][l[i - 1][j]]);
}
}
while(q--){
ans = 0;
int x, y;
cin >> x >> y;
if(x > y) swap(x, y);
int L = x, R = x;
for(int i = 20; i >= 0; i--){
int tL = min(l[i][L], l[i][R]);
int tR = max(r[i][L], r[i][R]);
if(tR < y){
ans += (1ll << i);
L = tL;
R = tR;
}
}
x = R, L = y, R = y;
for(int i = 20; i >= 0; i--){
int tL = min(l[i][L], l[i][R]);
int tR = max(r[i][L], r[i][R]);
if(tL > x){
ans += (1ll << i);
L = tL;
R = tR;
}
}
cout << ans << endl;
}
}
```