rt，时间 $O(n\log^2 n)$,空间 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+100;
int a[N];
namespace sg
{
	int ans,now;
	struct node
	{
		int *s;
	}t[N*4];
	inline void cover(const node &x,int len)
	{
		if(now<=x.s[len]-x.s[len-1])return (void)(ans+=x.s[len],now=x.s[len]-x.s[len-1]);
		if(now>=x.s[len]-x.s[len-1])return (void)(ans+=now*len);
		int l=1,r=len,mid,res=0;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(x.s[mid]-x.s[mid-1]<now)res=mid,l=mid+1;
			else r=mid-1;
		}
		ans+=(res)*now;
		ans+=x.s[len]-x.s[res];
		return (void)(now=x.s[len]-x.s[len-1]);
	}
	#define mid ((l+r)>>1)
	#define xx (t[x])
	#define ll (x<<1)
	#define rr (x<<1|1)
	inline void build(int l,int r,int x)
	{
		xx.s=new int[r-l+2];
		xx.s[0]=0;
		int noww=xx.s[1]=a[l];
		for(int i=l+1;i<=r;i++)noww=max(noww,a[i]),xx.s[i-l+1]=xx.s[i-l]+noww;
		if(l==r)return;
		build(l,mid,ll);
		build(mid+1,r,rr);
	}
	void find(int l1,int r1,int l,int r,int x)
	{
		if(l>=l1&&r<=r1){cover(xx,r-l+1);return;}
		if(l1<=mid)find(l1,r1,l,mid,ll);
		if(r1>mid)return find(l1,r1,mid+1,r,rr);
	}
	#undef mid
	#undef xx
	#undef ll
	#undef rr
}
using namespace sg;
signed main()
{
	// freopen("in.in","r",stdin);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,tt;
	cin>>n>>tt;
	for(int i=1;i<=n;i++)cin>>a[i];
	int lastans=0;
	int u,v,l,r;
	build(1,n,1);
	while(tt--)
	{
		cin>>u>>v;
		l=1+(u^lastans)%n,r=l+(v^(lastans+1))%(n-l+1);
		ans=now=0;
		find(l,r,1,n,1);
		cout<<(lastans=ans)<<'\n';
	}
	cerr<<n;
}