估计是WA了。

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10,S=1e3;
int l,r,n,m,cnt[S][S],d[S][N],st[S],ed[S],b[N],a[N],pos[N],bl,tot,pre[N],ne[N],A[N],B[N],la,lb;
struct p{int x,id;}c[N];
bool cmp(p a,p b){return a.x<b.x;}
int t[N];
int ask(int k){int ans=0;for(;k;k-=k&-k)ans+=t[k];return ans;}
void add(int k,int x){for(;k<=n;k+=k&-k)t[k]+=x;}
int merge(int *a,int *b,int la,int lb){
	int ans=0,j=0;
	for(int i=1;i<=la;i++){
		while(j<lb&&b[j+1]<a[i])j++;
		ans+=j;
	}
	return ans;
}
void init(){
	bl=160;
    for(int i=1;i<=n;i++)pos[i]=(i-1)/bl+1;
    tot=pos[n];
    for(int i=1;i<=tot;i++)st[i]=(i-1)*bl+1,ed[i]=i*bl;
    ed[tot]=n;
//    cout<<endl;
//    for(int i=1;i<=tot;i++)cout<<st[i]<<" "<<ed[i]<<endl;
//    cout<<endl;
    for(int i=1;i<=tot;i++){
    	for(int j=st[i];j<=ed[i];j++)b[a[j]]++;
    	for(int j=1;j<=n;j++)d[i][j]=d[i][j-1]+b[j];
	}
	for(int i=1;i<=tot;i++){
		int ans=0;
		for(int j=st[i];j<=ed[i];j++)add(a[j],1),ans+=pre[j]=(j-st[i]+1)-ask(a[j]);
		memset(t,0,sizeof(t));
		for(int j=ed[i];j>=st[i];j--)add(a[j],1),ne[j]=ask(a[j]-1);
		memset(t,0,sizeof(t));
		cnt[i][i]=ans;
	}	
	for(int i=1;i<=tot;i++){
		for(int j=st[i];j<=ed[i];j++)c[j]={a[j],j};
		sort(c+st[i],c+ed[i]+1,cmp);
	}
	for(int len=2;len<=tot;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			la=lb=0;
			for(int k=st[i];k<=ed[i];k++)A[++la]=c[k].x;
			for(int k=st[j];k<=ed[j];k++)B[++lb]=c[k].x;
			cnt[i][j]=cnt[i][j-1]+cnt[i+1][j]-cnt[i+1][j-1]+merge(A,B,la,lb);
		}
	}
//	for(int i=1;i<=tot;i++)for(int j=i;j<=tot;j++)printf("f[%d][%d]=%d\n",i,j,cnt[i][j]);
//	for(int i=1;i<=n;i++)cout<<pre[i]<<" "<<ne[i]<<endl;

}
int get(int l,int r){
	int L=pos[l],R=pos[r],ans=0;
	la=0,lb=0;
	if(L==R){
//		cout<<"!!!\n";
		for(int i=st[L];i<=ed[L];i++){
			if(c[i].id>=l&&c[i].id<=r)B[++lb]=c[i].x;
			if(c[i].id<l)A[++la]=c[i].x;
		}
		for(int i=l;i<=r;i++)ans+=pre[i];
		ans=pre[r]-pre[l-1]-merge(A,B,la,lb);
	}else{
//		cout<<"$$$\n";
		ans=cnt[L+1][R-1];
//		cout<<ans<<endl;
		for(int i=l;i<=ed[L];i++)ans+=d[R-1][a[i]-1]-d[L][a[i]-1],ans+=ne[i];
		for(int i=st[R];i<=r;i++)ans+=(ed[R-1]-st[L+1]+1)-(d[R-1][a[i]]-d[L][a[i]]),ans+=pre[i];
		for(int i=st[L];i<=ed[L];i++)if(c[i].id>=l)A[++la]=c[i].x;
		for(int i=st[R];i<=ed[R];i++)if(c[i].id<=r)B[++lb]=c[i].x;
		ans+=merge(A,B,la,lb);
	}
	return ans;
} 
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    int ans=0;
    while(m--){
    	cin>>l>>r;
    	l^=ans,r^=ans;
    	ans=get(l,r);
    	cout<<ans<<endl;
	}
}