源代码：

#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int x=0;register char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x;
}
inline void wr(int x)
{
    if(x>=10)wr(x/10);
    putchar(x%10^'0');
}
inline void wr(int x,char c)
{wr(x);putchar(c);}
#define cn const
#define N 500001
struct xx{int a,b;xx(){}};
struct xxx{int a,b,i;xxx(){}xxx(cn int&a,cn int&b,cn int&i):a(a),b(b),i(i){}};
int b[N];xx a[N];
int nxt[19][N];xxx st[N];int h;
int main()
{
    ios::sync_with_stdio(false);
    cn int n=re();int q=re();
    for(int i=1;i<=n;++i)b[i]=re();
    for(int i=1;i<=n;++i){a[i].a=b[i];a[i].b=re();}
    for(int i=1;i<=n;++i)
    {
        while(h&&(a[i].a==st[h].a||a[i].b>=st[h].b))
            nxt[0][st[h--].i]=i;
        st[++h]=xxx(a[i].a,a[i].b,i);
    }
    for(int j=1;j<=__lg(n);++j)
    for(int i=1;i<=n;++i)
        nxt[j][i]=nxt[j-1][nxt[j-1][i]];
    cn int er[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
    int s,p;
    while(q --> 0)
    {
        p=re();cn int r=re();
        s=1;
        for(int j=__lg(r-p);j>=0;--j)
            if(nxt[j][p]&&nxt[j][p]<=r){p=nxt[j][p];s+=er[j];}
        wr(s,10);
    }
    return 0;
}

提交记录：R73327424