记录编号	616940	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3653.[NOI Online 2022 1st]丹钓战	最终得分	100
用户昵称	zcx	是否通过	通过
代码语言	C++	运行时间	9.934 s
提交时间	2026-07-02 15:24:06	内存使用	136.65 MiB

#include<bits/stdc++.h>
#define int long long
#define M ((L + R)>>1)
using namespace std;
const int N = 5e5 + 5;
const int T = N * 30;

int n,q,tot = 0;
int a[N],b[N],f[N],rt[N];
int lc[T],rc[T],cnt[T];

void build(int &p,int L,int R){
    p = ++tot;cnt[p] = 0;
    if(L == R) return;
    build(lc[p],L,M);build(rc[p],M + 1,R);
}

void add(int p,int &q,int L,int R,int x){
    q = ++tot;
    lc[q] = lc[p];rc[q] = rc[p];cnt[q] = cnt[p] + 1;
    if(L == R) return;
    if(x <= M) add(lc[p],lc[q],L,M,x);
    else add(rc[p],rc[q],M + 1,R,x);
}

int ask(int p,int L,int R,int x){
    if(L == R) return cnt[p];
    if(x <= M) return ask(lc[p],L,M,x);
    return ask(rc[p],M + 1,R,x) + cnt[lc[p]];
}

signed main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    build(rt[0],0,n - 1);
    for(int i = 1;i <= n;i++) cin>>a[i];
    for(int i = 1;i <= n;i++) cin>>b[i];
    stack<int> s;f[1] = 0;s.push(0);
    for(int i = 1;i <= n;i++){
        while(!s.empty() && (a[i] == a[s.top()] || b[s.top()] <= b[i])) s.pop();
        if(s.empty()) f[i] = 0;
        else f[i] = s.top();
        add(rt[i - 1],rt[i],0,n - 1,f[i]);
        s.push(i);
    }
    while(q--){
        int l,r;cin>>l>>r;
        cout<<(ask(rt[r],0,n - 1,l - 1) - ask(rt[l - 1],0,n - 1,l - 1))<<'\n'; 
    }
    return 0;
}