题意

给定长度为 的序列 ，与 个询问求以下函数的返回值：

f(l,r)=
    if 1==l && r==n
        return 0
    else
        return f(min{A[l]...A[r]},max{A[l]...A[r]})+1

思路

首先需要一个重要的性质：若干个相交的区间迭代相同次数的 得到的若干区间仍然是相交的。

这个可以通过两个区间的情况以及一次迭代归纳证明。

可以进一步推广：迭代后的区间并等于迭代前的区间的并的迭代。

这个是显然的，因为第一次迭代之后是全相交的，那么必然连续。因为最小最大值的可重复贡献以及结合律，迭代一次必然相等，然后归纳即可。

那么就可以考虑将区间拆成 的形式，这样区间个数就只有 个了，只要维护出这 个区间按照迭代次数倍增的结果即可二分迭代次数求出答案。

显然直接按照定义式转成 RMQ 问题即可。

CODE

这题如果写一般的单 RMQ 是 的，会有点卡常。

这里写了线性 RMQ，时间复杂度为 。

需要注意区间退化成单点的情况，这里的实现是直接再倍增了一个数组。

#include<cstdio>
#include<functional>
using namespace std;
const int N=100010,M=18,FSIZE=1<<26;
int n,m,p[M][N],a[M][N],b[M][N];
template<typename T>struct RMQ{
    int n,A[N],BS,S[M][N/(M-1)],in[N],Pos[N],Pre[N],Sub[N],F[N];
    int max(int x,int y){return(T()(x,y)?x:y);}
    void buildST(){
        for(int i=0;i<n;++i){
            in[i]=i/BS;
            if(!(i%BS)) S[0][in[i]]=0x7ffffff-max(0,0x7ffffff);
            S[0][in[i]]=max(S[0][in[i]],A[i]);
            Pos[i]=i&&in[i-1]==in[i]?Pos[i-1]+1:0;
        }
        for(int i=1,t=(n-1)/BS;i<=31-__builtin_clz(t);++i)
            for(int j=1;j+(1<<i)-1<=t;++j)
                S[i][j]=max(S[i-1][j],S[i-1][j+(1<<(i-1))]);
    }
    void buildSubPre(){
        for(int i=0;i<n;++i)
            Pre[i]=i&&in[i]==in[i-1]?max(Pre[i-1],A[i]):A[i];
        for(int i=n-1;~i;--i)
            Sub[i]=in[i]==in[i+1]?max(Sub[i+1],A[i]):A[i];
    }
    void buildBlock(){
        static int S[N],top;
        for(int i=0;i<n;++i){
            if(!i||in[i]!=in[i-1]) top=0;
            else F[i]=F[i-1];
            while(top&&T()(A[i],A[S[top]])) F[i]^=1<<Pos[S[top--]];
            F[S[++top]=i]|=1<<Pos[i];
        }
    }
    void init(int *a,int _n){
        if(!(n=_n)) return;
        for(int i=0;i<n;++i) A[i]=a[i];
        BS=(31-__builtin_clz(n))*1.5;
        buildST();
        buildSubPre();
        buildBlock();
    }
    int query(int l,int r){
        int bl=in[l],br=in[--r];
        if(bl!=br){
            int ans=max(Sub[l],Pre[r]);
            if(br-bl>1){
                int p=31-__builtin_clz(br-bl-1);
                ans=max(ans,max(S[p][bl+1],S[p][br-(1<<p)]));
            }
            return(ans);
        }
        return(A[l+__builtin_ctz(F[r]>>Pos[l])]);
    }
};
RMQ<less<int>> R0[M];
RMQ<greater<int>> R1[M];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
void build(int t){
    for(int i=0;i<n;++i) p[t][i]=p[t-1][p[t-1][i]];
    for(int i=0;i<n-1;++i){
        if(a[t-1][i]<b[t-1][i]){
            a[t][i]=R0[t-1].query(a[t-1][i],b[t-1][i]);
            b[t][i]=R1[t-1].query(a[t-1][i],b[t-1][i]);
        }else a[t][i]=b[t][i]=p[t-1][a[t-1][i]];
    }
    R0[t].init(a[t],n-1);
    R1[t].init(b[t],n-1);
}
int query(int l,int r){
    int re=0;
    for(int i=M-1;~i;--i){
        int x=R0[i].query(l,r),y=R1[i].query(l,r);
        if(0<x||y+1<n){
            l=x;
            r=y;
            re+=1<<i;
        }
        if(l==r) return(1<<18);
    }
    return(re+1);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(m);
    for(int i=0;i<n;++i) read(p[0][i]);
    for(int i=0;i<n-1;++i){
        a[0][i]=min(p[0][i],p[0][i+1])-1;
        b[0][i]=max(p[0][i],p[0][i+1])-1;
    }
    R0[0].init(a[0],n-1);
    R1[0].init(b[0],n-1);
    for(int i=1;i<M;++i) build(i);
    for(int i=1,l,r;i<=m;++i){
        read(l);read(r);
        if(l==1&&r==n){
            printf("0\n");
            continue;
        }
        if(l<r){
            int ans=query(l-1,r-1);
            if(ans==1<<18) ans=-1;
            printf("%d\n",ans);
        }else printf("-1\n");
    }
    return(0);
}