- 给定一个长度为(n)的序列，从位置(i)可以花一步到达左/右第一个满足(a_j>a_i)的位置(j)。
- 每次询问给定两个区间([A,B],[C,D])，询问从([A,B])中任选一个点出发进入([C,D])的最小步数，或判无解。
- (nle2 imes10^5,qle10^5,Ale B<Cle D)
最优的起始点
考虑我们如何选择最优的起始点，它肯定需要满足下面两个条件：
- 在([A,B])区间中，它的后面没有值比它大的位置。
- 它的值比([C,D])中最大值要小（否则肯定无法到达）。
然后我们发现取尽可能大的值肯定是更优的，所以我们就是要求出以(B)为结尾的单调栈中，下标大于等于(A)且值小于([C,D])中最大值的最大的元素所在位置。
单调栈中的位置就是(B)向左能走到的位置，因此其实只要倍增预处理出一个(pre_{i,j})表示从(i)向左走(2^j)步到达的位置，每次从(B)开始向左倍增找到最小的满足(xge A)且(a_x)小于([C,D])中最大值的(x)即可。
点到区间的策略
现在的问题就是求出从(x)到([C,D])的最少步数。
首先，如果(x)向右一步就到达了([C,D])，那么最少步数就是(1)。
否则，我们肯定要先想办法越过((B,C))中的最大值。
一个无脑做法（我一开始的做法）就是直接倍增往右走，然后发现实际上左右横跳可能可以让我们步数更少。
因此，我们的策略实际上应该是每次走向左右值较大的位置，预处理一个(w_{i,j})表示从(i)每次往值较大的方向走(2^j)步到达的位置。
然后我们就倍增(x)找到下一步就会大于等于((B,C))中的最大值的最后一个位置。
如果下一步到达的就是((B,C))中的最大值了，我们直接一步走到最大值，下一步就能走入([C,D])。
否则说明下一步将往左走，如果走到的值小于([C,D])中的最大值，我们也可以先往左走一步，然后下一步就能走入([C,D])。
不然，此时我们不可能再向左，故预处理一个(nxt_{i,j})表示从(i)向右走(2^j)步到达的位置，一路走到((B,C))中的最大值所在位置，然后下一步就能走入([C,D])。
代码：(O(nlogn))
#include <bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define LN 18
using namespace std;
int n,a[N+5],pre[N+5][LN+1],nxt[N+5][LN+1],w[N+5][LN+1],LG[N+5],Mx[N+5][LN+1];
I int Q(CI l,CI r) {if(l>r) return 0;RI k=LG[r-l+1];return max(Mx[l][k],Mx[r-(1<<k)+1][k]);}//询问区间最值
I bool cmp(CI x,CI y) {return a[x]<a[y];}//根据值排序
int T,S[N+5],id[N+5];void init(int _n,vector<int> H)//预处理
{
RI i,j;for(LG[0]=-1,n=_n,i=1;i<=n;++i) LG[i]=LG[i>>1]+1,Mx[i][0]=a[i]=H[i-1];a[0]=a[n+1]=1e9;
for(j=1;(1<<j)<=n;++j) for(i=1;i+(1<<j)-1<=n;++i) Mx[i][j]=max(Mx[i][j-1],Mx[i+(1<<j-1)][j-1]);//RMQ预处理
for(i=1;i<=n;++i) {W(T&&a[S[T]]<=a[i]) --T;//从左向右单调栈
for(pre[i][0]=S[T],j=1;j<=LN;++j) pre[i][j]=pre[pre[i][j-1]][j-1];S[++T]=i;}//向左走的倍增预处理
for(S[T=0]=n+1,i=0;i<=LN;++i) nxt[n+1][i]=n+1;
for(i=n;i>=1;--i) {W(T&&a[S[T]]<=a[i]) --T;//从右向左单调栈
for(nxt[i][0]=S[T],j=1;j<=LN;++j) nxt[i][j]=nxt[nxt[i][j-1]][j-1];S[++T]=i;}//向右走的倍增预处理
RI x;for(i=1;i<=n;++i) id[i]=i;sort(id+1,id+n+1,cmp);for(i=n;i;--i)//按值从大往小枚举
for(x=id[i],w[x][0]=a[pre[x][0]]>a[nxt[x][0]]?pre[x][0]:nxt[x][0],j=1;j<=LN;++j) w[x][j]=w[w[x][j-1]][j-1];//向高处走的倍增预处理
}
int minimum_jumps(int A,int B,int C,int D)//询问
{
++A,++B,++C,++D;RI i,v=Q(C,D),x=B;if(a[B]>=v) return -1;//如果B的值都超过[C,D]最大值
for(i=LN;~i;--i) pre[x][i]>=A&&a[pre[x][i]]<v&&(x=pre[x][i]);if(nxt[x][0]>=C) return 1;//倍增找到最优出发点；如果能一步到达
RI s=Q(B+1,C-1),t=0;if(s>v) return -1;for(i=LN;~i;--i) a[w[x][i]]<s&&(x=w[x][i],t|=1<<i);//找到下一步值就会大于等于最大值的位置
if(a[nxt[x][0]]==s) return t+2;if(a[pre[x][0]]<v) return t+2;//可以直接走下一步然后一步到达
for(i=LN;~i;--i) a[nxt[x][i]]<=s&&(x=nxt[x][i],t+=1<<i);return t+1;//只能向右，倍增走到最大值所在位置，然后一步到达
}