-
考虑每个点它能到达的点的集合,可以发现是个 \(V\) 字形的图案,因为每个点第一步只有 \(2\) 种选择。
然后暴力就是用单调栈求出每个点的两条出边后 \(bfs\) 一遍即可。
-
设 \(C...D\) 段最高的高度为 \(mx\),若 \(B...C-1\) 有比它高的则无解。
-
\(A...B\) 中只有后缀 \(max < mx\) 的范围可能有解,设为 \(A‘...B\)。
考虑 \(A‘...B\) 中最高的为 \(x\),\(x\) 左边的一定比它劣,而右边的向右第一步能走到的范围必定也在 \(x\) 的范围之内,不会更优。
-
于是转化为单点到区间的最短路径。
-
\(x\) 走 \(k\) 步到达的最左与最右为 \(l,r\),若 \(r < C\) 则答案一定比 \(k\) 大。
而这个可以通过倍增求出 \(k\) 使得 \(x\) 走 \(k + 1\) 步便会超过或到达 \(C\)。
- 若 \(h_l < h_r\),则答案为 \(k + 1\),直接从 \(r\) 向右走一步即可。
- 否则
- 若 \(l\) 向右一步到达的点在区间内部,则答案为 \(k + 1\)。
- 否则 \(r\) 只能一直向右走,可以单方向倍增求出答案。
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
typedef pair <int, int> pii;
const int N = 6e5 + 10;
int n, h[N], l[N][20], r[N][20], f[N][20], top, s[N], b[N];
pii g[N][20];
pii qmax_(int l, int r) {
int k = b[r - l + 1];
return max(g[l][k], g[r - (1<<k) + 1][k]);
}
void init(int N, vector <int> H) {
n = N, b[0] = -1;
for (int i = 1; i <= n; i++)
h[i] = H[i - 1], g[i][0] = pii(h[i], i), b[i] = b[i>>1] + 1;
for (int k = 1; k <= b[n]; k++)
for (int i = 1; i + (1<<k) - 1 <= n; i++)
g[i][k] = max(g[i][k - 1], g[i + (1<<k - 1)][k - 1]);
for (int i = 1; i <= n; i++) {
while (top && h[s[top]] < h[i])
top--;
l[i][0] = top ? s[top] : i;
s[++top] = i;
}
top = 0;
for (int i = n; i; i--) {
while (top && h[s[top]] < h[i])
top--;
f[i][0] = r[i][0] = top ? s[top] : i;
s[++top] = i;
}
for (int k = 1; k <= b[n]; k++)
for (int i = 1; i <= n; i++) {
l[i][k] = min(l[l[i][k - 1]][k - 1], l[r[i][k - 1]][k - 1]);
r[i][k] = max(r[l[i][k - 1]][k - 1], r[r[i][k - 1]][k - 1]);
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
int mx = qmax_(C, D).first, L = A, R = B + 1;
// cout<<mx<<‘ ‘<<qmax_(B, C - 1).first<<‘\n‘;
if (qmax_(B, C - 1).first > mx)
return -1;
while (L < R) {
int mid = (L + R)>>1;
if (qmax_(mid, R).first > mx)
L = mid + 1;
else
R = mid;
}
int x = qmax_(L, B).second, ans = 0, y = x;
for (int k = b[n]; k >= 0; k--)
if (max(r[x][k], r[y][k]) < C) {
ans += 1<<k;
int p = min(l[x][k], l[y][k]), q = max(r[x][k], r[y][k]);
x = p, y = q;
}
if (h[y] > h[x])
return ans + 1;
if (f[x][0] >= C && f[x][0] <= D)
return ans + 1;
for (int k = b[n]; k >= 0; k--)
if (f[y][k] < C)
y = f[y][k], ans += 1<<k;
return ans + 1;
}