偶遇卡常题 ylst1，强如怪物，拼尽全力，76pts，无法战胜。语言已经用了 C++98 O2，不知道为啥加了快读没啥效果。

76pts 是在评测机波动下的最好结果。

#include<bits/stdc++.h>
#pragma GCC9 optimize("Ofast")
#pragma GCC9 optimize("unroll-loops")
#pragma GCC9 target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100005,B=250,A=455;
int n,m,cx,cy,x[A],y[A],a[N],bl[N],L[A],R[A],pre[N],suf[N],f[A][N],c[N],tf[N],ts[N];
long long ans,g[A][A];
pair<int,int>t[N];
inline void update(int u,int w){for(;u<=n;u+=u&-u)c[u]+=w;}
inline int query(int u){int r=0;for(;u;u-=u&-u)r+=c[u];return r;}
inline int merge(int *a,int *b,int n,int m)
{
	int p1=1,p2=1,res=0;
	while(p1<=n&&p2<=m)
	{
		if(a[p1]<b[p2])p1++;
		else{res+=n-p1+1;p2++;}
	}
	return res; 
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)
	{
		t[i]=make_pair(a[i],i);
		bl[i]=(i-1)/B+1;
		if(!L[bl[i]])L[bl[i]]=i;
		R[bl[i]]=i;
	}
	for(int i=1,cnt;i<=bl[n];i++)
	{
		sort(t+L[i],t+R[i]+1);
		for(int j=L[i];j<=R[i];j++)
		{
			tf[j]=t[j].first;
			ts[j]=t[j].second;
		}
		cnt=0;
		for(int j=L[i];j<=R[i];j++)
		{
			update(a[j],1);
			cnt+=query(n)-query(a[j]);
			pre[j]=cnt;
		}
		g[i][i]=cnt;
		for(int j=L[i];j<=R[i];j++)
		{
			update(a[j],-1);
			suf[j]=cnt;
			cnt-=query(a[j]-1);
		}
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=bl[n];i++)for(int j=1,p=L[i],id;j<=n;j++)
	{
		id=t[j].second;
		while(p<=R[i]&&tf[p]<t[j].first)p++;
		if(id<L[i])f[i][id]=p-L[i];
		else if(id>R[i])f[i][id]=R[i]-p-(p<=R[i]&&t[j].first==tf[p])+1;
	}
	for(int i=1;i<=bl[n];i++)for(int j=2;j<=n;j++)f[i][j]+=f[i][j-1];
	for(int i=1,r;i<bl[n];i++)for(int j=1;j<=bl[n]-i;j++)
	{
		r=i+j;
		g[j][r]=g[j][r-1]+g[j+1][r]-g[j+1][r-1]+f[r][R[j]]-f[r][L[j]-1];
	}
	for(int i=1,l,r,ll,rr;i<=m;i++)
	{
		l=read()^ans;r=read()^ans;ll=bl[l];rr=bl[r];cx=cy=0;
		if(ll==rr)
		{
			for(int i=L[ll];i<=R[rr];i++)
			{
				if(l<=ts[i]&&ts[i]<=r)y[++cy]=tf[i];
				else if(ts[i]<l)x[++cx]=tf[i];
				ans=pre[r]-(l==L[ll]?0:pre[l-1])-merge(x,y,cx,cy);
			}
		}
		else
		{
			ans=g[ll+1][rr-1]+pre[r]+suf[l];
			for(int i=ll+1;i<rr;i++)ans+=f[i][R[ll]]-f[i][l-1]+f[i][r]-f[i][L[rr]-1];
			for(int i=L[ll];i<=R[ll];i++)if(ts[i]>=l)x[++cx]=tf[i];
			for(int i=L[rr];i<=R[rr];i++)if(ts[i]<=r)y[++cy]=tf[i];
			ans+=merge(x,y,cx,cy);
		}
		printf("%lld\n",ans);
	}
}