#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005, M = 655;
int n, m, b[N], L[M], R[M], num, pos[N], pre[N], suf[N], f[M][M], cnt[M][N], t[N], ans;
struct node{
	int val, id;
}a[N];
inline int read(){
	int q = 0, w = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		ch = getchar();
	}
	while(isdigit(ch)){
		q = q * 10 + (ch - '0');
		ch = getchar();
	}
	return q * w;
}
inline void write(int x){
	if(x > 9){
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
inline int lowbit(int x){
	return x & (-x);
}
inline void change(int x, int k){
	while(x <= n){
		t[x] += k;
		x += lowbit(x);
	}
}
inline int find(int x){
	int sum = 0;
	while(x){
		sum += t[x];
		x -= lowbit(x);
	}
	return sum;
}
inline bool cmp(node x, node y){
	return x.val < y.val;
}
inline int Mer(int x, int y, int xx, int yy){
	int be1 = x;
	int be2 = xx;
	int sum = 0;
	while(be1 <= y && be2 <= yy){
		if(b[be1] > b[be2]){
			sum += (y - be1 + 1);
			be2++;
		}else{
			be1++;
		}
	}
	return sum;
}
inline void init(){
	int T = 210; 
	for(register int i = 1;i <= n;++i){
		pos[i] = (i - 1) / T + 1;
		R[pos[i]] = i;
		if(L[pos[i]] == 0){
			num++;
			L[pos[i]] = i;
		}
	}
	for(register int i = 1;i <= num;++i){
		for(register int j = 1;j <= n;++j){
			cnt[i][j] = cnt[i - 1][j];
		}
		int tot = 0;
		for(register int j = L[i];j <= R[i];++j){
			change(a[j].val, 1);
			tot += (find(n) - find(a[j].val));
			pre[j] = tot;
		}
		f[i][i] = tot;
		for(register int j = L[i];j <= R[i];++j){
			suf[j] = tot;
			change(a[j].val, -1);
			tot -= (find(a[j].val - 1));
		}		
		sort(a + L[i], a + R[i] + 1, cmp);
		for(register int j = L[i];j <= R[i];++j){
			cnt[i][a[j].val]++;
			b[j] = a[j].val;
		}
	}
	for(register int i = 1;i <= num;++i){
		for(register int j = n - 1;j >= 1;j--){
			cnt[i][j] += cnt[i][j + 1];
		}
	}
	for(int len = 1;len <= num;len++){
		for(register int i = 1;i + len <= num;++i){
			register int j = i + len;
			f[i][j] = f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1] + Mer(L[i], R[i], L[j], R[j]);
		}
	}
}
inline int wor(int x, int y){
	int sum = 0;
	if(pos[x] == pos[y]){
		int be1 = 1, be2 = 401;
		int ed1 = 0, ed2 = 400;
		for(register int i = L[pos[x]];i <= R[pos[x]];++i){
			if(a[i].id >= x && a[i].id <= y){
				b[++ed2] = a[i].val;
			}
			if(a[i].id < x){
				b[++ed1] = a[i].val;
			}
		}
		if(x != L[pos[x]]){
			sum = -pre[x - 1];
		}
		sum += pre[y];
		sum -= Mer(be1, ed1, be2, ed2);
	}else{
		sum = f[pos[x] + 1][pos[y] - 1] + pre[y] + suf[x];
		int be1 = 1, be2 = 401;
		int ed1 = 0, ed2 = 400;
		for(register int i = L[pos[x]];i <= R[pos[x]];++i){
			if(a[i].id >= x){
				b[++ed1] = a[i].val;
				sum += (cnt[pos[y] - 1][1] - cnt[pos[y] - 1][a[i].val]) - (cnt[pos[x]][1] - cnt[pos[x]][a[i].val]);
			}
		}
		for(register int i = L[pos[y]];i <= R[pos[y]];++i){
			if(a[i].id <= y){
				b[++ed2] = a[i].val;
				sum += (cnt[pos[y] - 1][a[i].val + 1] - cnt[pos[x]][a[i].val + 1]);
			}
		}
		sum += Mer(be1, ed1, be2, ed2);
	}
	return sum;
}
signed main(){
	n = read(); m = read();
	for(register int i = 1;i <= n;++i){
		a[i].val = read();
		a[i].id = i;
	}
	init();
	while(m--){
		int x = read() ^ ans;
		int y = read() ^ ans;
		ans = wor(x, y);
		write(ans);
		puts("");
	}
	return 0;
}

现在第1,2,3个测试点都可能会寄

有无大佬帮忙看看卡常