講個笑話，這道題目我本來是在掃描線的題目里邊找到的，但我的方法跟掃描線沒有任何關系。

題意不多說了。

發現題目諧音單調棧，但是并沒有什么幫助，因為題干在描述的不就是一個單調棧嘛？

不可否定的，對于 \([L,R]\)，一個個位置 \(A[L]\) 一定是成功的。

我們只需要判斷什么時候會把 \(A[L]\) 給彈出去，這個位置就是下一個成功的。

對于下一個，這依然是一個相同的問題罷了。

我們要做的工作實際上就是一直跳。

用倍增優化一下就好了，\(O(nlogn)\)

就沒有了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+115;
int dp[MN][20], stk[MN], top;
int n, q, a[MN], b[MN];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>q;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n; ++i) cin>>b[i];
	for(int i=1; i<=n; ++i){
		while(top&&((a[i]==a[stk[top]])||(b[i]>=b[stk[top]]))){
			dp[stk[top]][0]=i; --top;
		}
		stk[++top]=i;
	}
	for(int j=1; j<20; ++j){
		for(int i=1; i<=n; ++i){
			dp[i][j]=dp[dp[i][j-1]][j-1];
		}
	}
	for(int j=1; j<=q; ++j){
		int ans=0, l, r;
		cin>>l>>r;
		for(int i=19; i>=0; --i){
			if(dp[l][i]&&dp[l][i]<=r){
				ans+=1<<i; l=dp[l][i];
			}
		}
		cout<<ans+1<<'\n';
	}

	return 0;
}