-
Sub1：\(C-B\)。
-
Sub2 / 3 / 4：考虑 \(i \to lef_i,rig_i\) 连边，每次对 \(S \in [A,B]\) 的点 dis 设为 \(0\)，BFS 即可，\(O(nq)\)。
-
Sub5：首先如果 \((A,C)\) 存在 \(h_x \gt h_C\) 那么一定无解。考虑一个贪心策略：每次在 \(i\) 向高度比 \(h_C\) 更低的、高度更高的那一边跳，这个显然是对的（在点 \(i\) 考虑左右两个单调序列），问题是如何满足比 \(h_C\) 更低。注意到，如果在 \(i\) 无法向左跳，那么在之后跳到的点也一定无法向左跳，故之后一直向右跳，这部分的答案很容易用单调栈预处理。于是问题变为找出这样贪心跳的过程中第一个 \(h_{lef} \gt h_C\) 的点 \(x\)，并且求只保留 \(i \to \max(lef,rig)\) 的边，\(i \to x\) 的距离，注意到这样连边每个点有且只有一条出边，所以连成一个森林，
那么距离是容易预处理的那么可以倍增跳求距离。对于找 \(x\)，就是在祖先链上找到最深的 \(h_{lef} \gt h_c\) 的点，这个也是可以倍增做到 \(O(q \log n)\) 的。 -
Sub6：正着做就会有 \(O(n)\) 个 \(x\)，所以只能倒着做（，连边变为 \(i \to \min(lef,rig)\)，并且这里如果 \(i\) 能一步跳到 \(y \in [l,r]\) 那么就不会贪心地往另一边更低的走，那找终点 \(x\) 就会变成祖先链上最深的满足 \(h_{rig} \lt \min_{i=A}^{B} h_i\) 或 \(lef \in [A,B]\) 的点（注意 \(rig \in [A,B]\) 是不可能作为最后一步的起点的），你可以树剖之后对每条重链建动态开点线段树，维护的是区间 \(\max dep\) 以及对应的编号，那么这个也是可以 \(O(q \log n)\) 的，同理上面那个 Subtask 的倍增也是可以换成树剖 + 线段树二分的。
但是这两个 Subtask 的做法都强依赖于固定了一边的端点（
所以虽然貌似有 81 pts 了但是好像跟正解没什么关系（
草（，关系很大。
起点一定是 \(\max([A,B])\)（这里 \(A\) 是修正后的左端点，即极小的满足 \(h_A \lt \max([C,D])\) 的 \(A\)）（其实这是十分显然的，不知道为什么有人看不出来）。
所以倒过来使用 Sub6 的做法就做完了。于是你有了一个时间 \(O(q \log n)\) 空间 \(O(n \log n)\) 的 neuze 做法，感觉不是很好写 好写阿，很好写阿。
事实上你 Sub6 的做法也可以倍增 /yun
这里就考虑从 \(\max([A,B])\) 正着跳到 \([C,D]\) 里，考虑如果 \(rig_x \in [C,D]\) 那么 \(h_{rig_x}\) 满足什么条件，其实就是 \(h_{rig_x} \in (\max_{i=B}^{C-1} h_i , \max_{i=C}^{D} h_i]\)（因为一定有 \(\text{max of } [B,C-1] \le \text{max of } [C,D]\)），那么因为跳的过程中 \(h_{rig}\) 是递增的，我们先倍增地跳到这个区间里，然后判断是否合法，是就直接跳进去求出答案；否则再继续跳到 \(h_{lef} \gt \max([C,D])\) 的那个祖先就行了。因为有 \(h\) 的单调性，你甚至不需要建出上文所说的森林（
找性质应该找全（
注意边界（nxt / rig[0 ~ 17][n+1]），WA 了一万发（
constexpr int Q = 200003, oo = 2e9;
int n, Log2[Q], a[Q], seq[Q];
__attribute__((constructor)) static void
___________(){ for(int i = 2; i < Q; ++i) Log2[i] = Log2[i>>1] + 1; }
template<int N> struct MaxList {
static const int LOG = 31-__builtin_clz(N); int st[LOG+1][N];
inline int MAX(int i, int j){ return a[i] > a[j] ? i : j; }
inline void Make(int n, int *a){ copy(a+1, a+n+1, st[0]+1); for(int j = 1; j <= Log2[n]; ++j) for(int i = n-(1<<j-1); i >= 1; --i) st[j][i] = MAX(st[j-1][i], st[j-1][i+(1<<j-1)]); }
inline int Max(int l, int r){ int K = Log2[r-l+1]; return MAX(st[K][l], st[K][r-(1<<K)+1]); }
}; MaxList<Q> st; int L[Q], R[Q], nxt[18][Q], rig[18][Q], sta[Q], top;
void init(int N, vector<int> H) {
n = N; for(int i = 1; i <= n; ++i) seq[i] = i;
copy(begin(H), end(H), a+1), st.Make(n, seq);
sta[top = 1] = 0, a[0] = +oo;
for(int i = 1; i <= n; sta[++top] = i, ++i)
for(L[i] = sta[top]; a[sta[top]] <= a[i]; L[i] = sta[--top]);
sta[top = 1] = n+1, a[n+1] = +oo;
for(int i = n; i >= 1; sta[++top] = i, --i)
for(R[i] = sta[top]; a[sta[top]] <= a[i]; R[i] = sta[--top]);
for(int i = 1; i <= n; ++i)
rig[0][i] = R[i], nxt[0][i] = a[L[i]] > a[R[i]] ? L[i] : R[i];
rig[0][n+1] = nxt[0][n+1] = n+1;
for(int j = 1; j < 18; ++j)
for(int i = 1; i <= n+1; ++i)
nxt[j][i] = nxt[j-1][nxt[j-1][i]], rig[j][i] = rig[j-1][rig[j-1][i]];
// fprintf(stderr, "!!!! ");
// for(int i = n; i >= 1; --i) fprintf(stderr, "(%d , %d)%c", R[i], dep[i], " \n"[i == 1]);
}
int minimum_jumps(int A, int B, int C, int D) {
// fprintf(stderr, "sol [%d , %d] , [%d , %d]\n", A, B, C, D);
++A, ++B, ++C, ++D;
int res = 0, ptr = 0, pos = st.Max(C, D);
int Upd1 = a[st.Max(B, C-1)], Upd2 = a[pos];
int l = A, r = B, mid, ans = B+1;
while(l <= r) mid = l+r>>1, a[st.Max(mid, B)] < Upd2 ? (ans = mid, r = mid-1) : (l = mid+1);
if(ans > B || Upd1 > Upd2) return -1; ptr = st.Max(ans, B);
for(int j = 17; j >= 0; --j)
if(a[nxt[j][ptr]] <= Upd1) res += 1<<j, ptr = nxt[j][ptr];
if(ptr >= C && ptr <= D) return res; // 已经在区间内
if(R[ptr] >= C && R[ptr] <= D) return res + 1; // 跳一步
if(R[nxt[0][ptr]] >= C && R[nxt[0][ptr]] <= D) return res + 2; // 跳两步
for(int j = 17; j >= 0; --j)
if(rig[j][ptr] < C) res += 1<<j, ptr = rig[j][ptr]; // 跳祖先
return res + 1;
}