RT，看得第二篇题解

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+5;
int n,Q;
int a[N];
LL f[N][23],nxt[N][23];
int s[N],top;
int main(){
	cin>>n>>Q;
	int MX=log2(n)+1;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=n;i++){
		while(top&&a[s[top]]<a[i]){
			nxt[s[top]][0]=i;
			--top;
		}
		s[++top]=i;
	}
	while(top) nxt[s[top--]][0]=n+2;
	nxt[n+1][0]=nxt[n+2][0]=n+2;
	for(int i=1;i<=n;i++)
		f[i][0]=1LL*a[i]*(nxt[i][0]-i);
	
	for(int j=1;j<=MX;j++){
		for(int i=1;i<=n+2;i++)
			nxt[i][j]=n+2;
		for(int i=1;i+(1<<j)-1<=n;i++){
			nxt[i][j]=nxt[nxt[i][j-1]][j-1];
			f[i][j]=f[i][j-1]+f[nxt[i][j-1]][j-1];			
		}
	}
	int u,v;
	LL ans=0;
	while(Q--){
		cin>>u>>v;
		int l=1+(u^ans)%n, r=l+(v^(ans+1))%(n-l+1);
		int pos=l;
		ans=0;
		for(int i=MX;i>=0;i--){
			if(nxt[pos][i]-1>r) continue;
			ans+=f[pos][i];
			pos=nxt[pos][i];
		}
		ans+=a[pos]*(r-pos+1);
		cout<<ans<<"\n";
	}
	return 0;
}