8分求条A#4，其它全RE

#include<bits/stdc++.h>
//#define endl "\n"
using namespace std;
int n,m,sum[400][100005],lk[400],rk[400],idk[200005],last,num[400],suma[400][325],sumb[400][100005],g[100005][400],kuainum[329][329][329]; 
long long p[400][400];
struct node{
	int id,x;
}a[100005],b[100005];
bool cmp(node s1,node s2){
	return s1.x<s2.x;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].id=i;
		b[i]=a[i];
	}
	int kuai=sqrt(n),len=sqrt(n);
	if(kuai*kuai!=n) kuai++,len++;
	for(int i=1;i<=kuai;i++){
		lk[i]=rk[i-1]+1,rk[i]=min(n,lk[i]+len-1);
		sort(b+lk[i],b+rk[i]+1,cmp);
		for(int j=lk[i];j<=rk[i];j++){
			idk[j]=i;
			sum[i][a[j].x]++;
		}
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1];
		}
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i-1][j];
		}
		for(int j=lk[i];j<=rk[i];j++){
			int cnt=0;
			for(int k=lk[i];k<j;k++){
				if(a[k].x>a[j].x) num[i]++,cnt++;
			}
			suma[i][j-lk[i]+1]=suma[i][j-lk[i]+1-1]+cnt;
		}
		for(int j=rk[i];j>=lk[i];j--){
			int cnt=0;
			for(int k=j+1;k<=rk[i];k++){
				if(a[j].x>a[k].x) cnt++;
			}
			sumb[i][j-lk[i]+1]=sumb[i][j-lk[i]+1+1]+cnt;
		}
		for(int j=lk[i];j<=rk[i];j++){
			for(int k=lk[i];k<j;k++){
				if(a[k].x>a[j].x){
					g[j][k-lk[i]+1]=g[j][k-lk[i]]+1;
				}else{
					g[j][k-lk[i]+1]=g[j][k-lk[i]];
				}
			}
		}
		for(int j=lk[i];j<=rk[i];j++){
			for(int k=j+1;k<=rk[i];k++){
				kuainum[i][j-lk[i]+1][k-lk[i]+1]=kuainum[i][j-lk[i]+1][k-lk[i]]+g[k][k-lk[i]]-g[k][j-lk[i]]; 
			}
		}
	}
	for(int i=1;i<=kuai;i++){
		for(int j=i;j<=kuai;j++){
			p[i][j]=p[i][j-1]+num[j];
			for(int k=lk[j];k<=rk[j];k++){
				int t=sum[j-1][n]-sum[j-1][a[k].x]-(sum[i-1][n]-sum[i-1][a[k].x]);
				p[i][j]+=t;
			}
		}
	}
	while(m--){
		int l,r;
		long long ans=0;
		cin>>l>>r;
		l^=last,r^=last;
        //if(l==0||l>=n+1||r==0||r>=n+1||l>r) return 0;
		int idl=idk[l],idr=idk[r];
		if(idl==idr){
			ans=kuainum[idl][l-lk[idl]+1][r-lk[idr]+1];
			last=ans;
			cout<<ans<<endl;
			continue;
		}
		ans=p[idl+1][idr-1];
		ans+=sumb[idl][l-lk[idl]+1]+suma[idr][r-lk[idr]+1];
		if(idl+1<=idr-1){
			for(int i=lk[idr];i<=r;i++){
				long long t=sum[idr-1][n]-sum[idr-1][a[i].x]-(sum[idl+1-1][n]-sum[idl+1-1][a[i].x]);
				ans+=t;
			}
			for(int i=l;i<=rk[idl];i++){
				long long  t=sum[idr-1][a[i].x-1]-sum[idl+1-1][a[i].x-1];
				ans+=t;
			}
		}
		int lt=lk[idr]-1,cnt=0;
		for(int i=lk[idl];i<=rk[idl];i++){
			if(b[i].id<l||b[i].id>r) continue;
			while(lt+1<=rk[idr]){
				if(b[lt+1].id<l||b[lt+1].id>r) lt++;
				else if(b[lt+1].x<b[i].x){
					cnt++,lt++;
				}
				else{
					break;
				} 
			}
			ans+=cnt;
		}
		last=ans;
		cout<<ans<<endl;
	}
	return 0;
}