RT，明明是一个普普通通的线段树，没想到被卡空间了（难道是出题人要故意卡掉线段树做法吗）

内存限制125MB

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+1;
int n,m,las,a,b,ll,rr,bas;
struct Tree{
	int maxn,minx;
	long long sum;
}tree[N*2];
int finds(int id,int l,int r)
{
	if(tree[id].maxn<=bas)
		return bas*(r-l+1);
	if(tree[id].minx>=bas)
		return tree[id].sum;
	int mid=(l+r)/2;
	if(bas<=tree[id*2].maxn)
		return finds(id*2,l,mid)+tree[id].sum-tree[id*2].sum;
	return bas*(mid-l+1)+finds(id*2+1,mid+1,r);
}
void pushup(int id,int l,int r)
{
	tree[id].maxn=max(tree[id*2].maxn,tree[id*2+1].maxn);
	bas=tree[id*2].maxn;
	tree[id].minx=tree[id*2].minx;
	int mid=(l+r)/2;
	tree[id].sum=tree[id*2].sum+finds(id*2+1,mid+1,r);
}
void build(int id,int l,int r)
{
//	tree[id].l=l;tree[id].r=r;
	if(l==r)
	{
		int a;
		scanf("%d",&a);
		tree[id].maxn=tree[id].minx=tree[id].sum=a;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(id,l,r);
}
int find(int id,int l,int r)
{
	if(ll<=l&&r<=rr)
	{
		int cur=finds(id,l,r);
		bas=max(bas,tree[id].maxn);
		return cur;
	}
	int mid=(l+r)/2;
	int sum=0;
	if(ll<=mid)sum+=find(id*2,l,mid);
	if(rr>mid)sum+=find(id*2+1,mid+1,r);
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
//	for(int i=1;i<=n;++i)scanf("%lld",&num[i]);
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		ll=1+(a^las)%n;
		rr=(b^(las+1))%(n-ll+1)+ll;
		bas=0;
		las=find(1,1,n);
		printf("%d\n",las);
	}
	return 0;
}