我是不是咕咕咕？还是被卡常！~

#include<cstdio>
#include<iostream>
#define N 100005
#define M 325
#define K N/M+15
using namespace std;
typedef long long LL;
int read()
{
    int ans=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;'0'<=c&&c<='9';c=getchar())
        ans=ans*10+c-'0';
    return ans;
}
int n,m,cnt=0; 
int a[N],c[N],bl[N],d[N],l[K],r[K],ord[N],w[N],deb[N];
LL Tree[3*N]; 
LL f[K][K];
LL g[N][K],lstans=0,ans=0;
LL le[N],ri[N];
void merge(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)/2,k=bl[l];
	merge(l,mid);
	merge(mid+1,r);
	int i=l,j=mid+1,x=l-1;
	while(i<=mid||j<=r)
		if(i>mid||(j<=r&&c[j]<c[i])) 
		{
			w[++x]=ord[j];
			d[x]=c[j++];
			f[k][k]+=mid-i+1;
		}
		else w[++x]=ord[i],d[x]=c[i++];
	for(int i=l;i<=r;i++)
		c[i]=d[i],ord[i]=w[i];
}
LL init(int x,int y)
{
	int i=l[x],j=l[y];
	LL ans=0;
	while(i<=r[x]||j<=r[y])
		if(i>r[x]||(j<=r[y]&&c[j]<c[i])) ans+=g[ord[j++]][x]=r[x]-i+1;
		else g[ord[i++]][y]=j-l[y];
	return ans;
}
LL ans_deb=0;
void Mer_deb(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)/2;
	Mer_deb(l,mid);
	Mer_deb(mid+1,r);
	int i=l,j=mid+1,x=l-1;
	while(i<=mid||j<=r)
		if(i>mid||(j<=r&&deb[j]<deb[i])) d[++x]=deb[j++],ans_deb+=mid-i+1;
		else d[++x]=deb[i++];
	for(int i=l;i<=r;i++)
		deb[i]=d[i];
}
LL Mer(int l0,int r0,int l1,int r1)
{
	int i=l0,j=l1;
	LL ans=0;
	while(i<=r0||j<=r1)
		if(i>r0||(j<=r1&&c[j]<c[i])) j++,ans+=r0-i+1;
		else i++;
	return ans;
}
void ins(int x)
{
	for(;x<=n;x+=x & (-x))
		Tree[x]++;	
}
LL q(int x)
{
	LL ans=0;
	for(;x;x-=x & (-x))
		ans+=Tree[x];
	return  ans;	
} 
void dec(int x)
{
	for(;x<=n;x+=x & (-x))
		Tree[x]--;	
}
int main()
{
	n=read(),m=read();
	l[cnt=1]=1;
	for(int i=1;i<=n;ord[i]=i,i++)
	{
		if(i%M==0)
		{
			r[cnt]=i-1;
			l[++cnt]=i;
		}
		bl[i]=cnt;
		c[i]=a[i]=read();
	}
	r[cnt]=n; 
	for(int i=1;i<=cnt;i++)
		merge(l[i],r[i]);
	for(int x=1;x<=cnt;x++)
	{
		for(int i=l[x];i<=r[x];i++)
		{
			le[i]=i-l[x]-q(a[i])+((i==l[x])?0:le[i-1]);
			ins(a[i]);
		}
		for(int i=l[x];i<=r[x];i++)
			dec(a[i]);
		for(int i=r[x];i>=l[x];i--)
		{
			ri[i]=q(a[i])+((i==r[x])?0:ri[i+1]);
			ins(a[i]);
		}
		for(int i=l[x];i<=r[x];i++)
			dec(a[i]);
	}
	for(int i=1;i<cnt;i++)
		for(int j=i+1;j<=cnt;j++)
			f[j][i]=f[i][j]=init(i,j);
	for(int i=1;i<=cnt;i++)
		for(int j=2;j<=cnt;j++)
			f[i][j]+=f[i][j-1];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=cnt;j++)
			g[i][j]+=g[i][j-1];
	while(m--)
	{
		ans=0;
		int L=read()^lstans,R=read()^lstans;
		if(bl[L]==bl[R])
		{
			int k=l[bl[L]];
			ans+=le[R]-((L==k)?0:le[L-1]);
			int tot=0;
			for(int i=l[bl[L]];i<=r[bl[L]];i++)
				if(k<=ord[i]&&ord[i]<L) c[++tot]=a[ord[i]];
			int tot1=tot;
			for(int i=l[bl[L]];i<=r[bl[L]];i++)
				if(L<=ord[i]&&ord[i]<=R) c[++tot1]=a[ord[i]];
			if(k!=L) ans-=Mer(1,tot,tot+1,tot1);
		}
		else
		{
			int sql=bl[L]+1,sqr=bl[R]-1;
			int k=bl[L];
			ans+=ri[L]+le[R];
			for(int i=L;bl[i]==k;i++)
				ans+=g[i][sqr]-g[i][sql-1];
			k=bl[R];
			for(int i=R;bl[i]==k;i--)
				ans+=g[i][sqr]-g[i][sql-1];
			int tot=0;
			for(int i=l[bl[L]];i<=r[bl[L]];i++)
				if(ord[i]>=L) c[++tot]=a[ord[i]];
			int tot1=tot;
			for(int i=l[bl[R]];i<=r[bl[R]];i++)
				if(ord[i]<=R) c[++tot1]=a[ord[i]];
			ans+=Mer(1,tot,tot+1,tot1);
			for(int i=sql;i<=sqr;i++)
				ans+=f[i][sqr]-f[i][i-1];		
		}
		printf("%lld\n",lstans=ans);
	}
	return 0;
}