写了一个疑似单调队列的做法,开了O2民间能过但是官方的过不了求助各位帮忙看一下谢谢大佬
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
int a[maxn],b[maxn];
int main(){
// freopen("stack.in","r",stdin);
// freopen("stack.out","w",stdout);
ios::sync_with_stdio(0);
int n,q;
cin >> n >> q;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<=n;i++){
cin >> b[i];
}
a[n+1] = 10000000;
b[n+1] = 10000000;
stack<int>s;
int w[maxn];
for(int i=1;i<=n+1;i++){
//我比你高 = 我的b>你的b或者我的a == 你的a
while(!s.empty()){
int x = s.top();
if(b[i]>=b[x]){
w[x] = i;
s.pop();
}
else if(a[i] == a[x]){
w[x] = i;
s.pop();
}
else break;
}
s.push(i);
}
for(int i=1;i<=q;i++){
int l,r;
cin >> l >> r;
int ans = 0;
for(int j = l;j<=r;){
ans++;
j = w[j];
}
cout << ans << '\n';
}
return 0;
}