TLE #1, 2, 3 求大手子卡常/ll

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	return x * f;
}
// mt19937_64 sj(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<LL> u0(0, 1ll << 60);

const int N = 100010, B = 600, M = N / B + 5;

int n, m, p[N], bl;
int L[N], R[N], id[N], tmp1[N], tmp2[N];
int pre[N], suf[N], g[M][N];
LL f[M][M];
PII b[N];

struct BIT {
	int tr[N];
	void init() { memset(tr, 0, sizeof tr); }
	void modify(int x, int k) {
		for (; x <= n; x += lowbit(x)) tr[x] += k;
	}
	int query(int x) {
		int res = 0;
		for (; x; x -= lowbit(x)) res += tr[x];
		return res;
	}
} sgt;

LL calc(int *A, int *B, int la, int lb) {
	int res = 0, i = 1, j = 1;
	while (i <= la && j <= lb) 
		if (A[i] < B[j]) i ++;
		else res += la - i + 1, j ++;
	return res;
}

void init() {
	int l = 1, r = min(B, n);
	for (int i = 1; l <= n; ++ i, l = r + 1, r = min(n, l + B - 1)) {
		L[i] = l, R[i] = r, bl ++;
		for (int j = l; j <= r; j ++) id[j] = i;
	}
	for (int i = 1; i <= bl; ++ i) {
		sort(b + L[i], b + R[i] + 1);
		sgt.init(); 
		LL res = 0;
		for (int j = L[i]; j <= R[i]; ++ j) {
			res += sgt.query(n) - sgt.query(p[j] - 1);
			pre[j] = res;
			sgt.modify(p[j], 1);
		}
		res = 0;
		sgt.init();
		for (int j = R[i]; j >= L[i]; -- j) {
			res += sgt.query(p[j] - 1);
			suf[j] = res;
			sgt.modify(p[j], 1);
		}
		f[i][i] = suf[L[i]];
		for (int j = 1; j < L[i]; ++ j) g[i][j] = sgt.query(p[j] - 1);
		for (int j = R[i] + 1; j <= n; ++ j) g[i][j] = sgt.query(n) - sgt.query(p[j]);
		for (int j = 1; j <= n; j ++) g[i][j] += g[i][j - 1];
	}
	for (int len = 2; len <= bl; ++ len)
		for (int i = 1; i + len - 1 <= bl; ++ i) {
			int j = i + len - 1;
			f[i][j] = f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1] + g[j][R[i]] - g[j][L[i] - 1];
		}
}

LL query(int l, int r) {
	LL ans = 0;
	int pl = id[l], pr = id[r];
	if (pl == pr) {
		if (l == L[pl]) return pre[r];
		int la = 0, lb = 0;
		for (int i = L[pl]; i <= R[pl]; i ++) 
			if (l <= b[i].second && b[i].second <= r) tmp2[++ lb] = b[i].first;
			else if (b[i].second < l) tmp1[++ la] = b[i].first;
		ans = pre[r] - pre[l - 1] - calc(tmp1, tmp2, la, lb);
		return ans;
	}
	ans = suf[l] + f[pl + 1][pr - 1] + pre[r]; 
	for (int i = pl + 1; i <= pr - 1; i ++) 
		ans += g[i][R[pl]] - g[i][l - 1] + g[i][r] - g[i][L[pr] - 1];
	int la = 0, lb = 0;
	for (int i = L[pl]; i <= R[pl]; i ++) 
		if (b[i].second >= l) tmp1[++ la] = b[i].first;
	for (int i = L[pr]; i <= R[pr]; i ++)
		if (b[i].second <= r) tmp2[++ lb] = b[i].first;
	ans += calc(tmp1, tmp2, la, lb);
	return ans;   
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++ i) p[i] = read(), b[i] = {p[i], i};
	init();
	LL lst = 0;
	for (int i = 1; i <= m; ++ i) {
		int l = read() ^ lst, r = read() ^ lst;
		lst = query(l, r);
		printf("%lld\n", lst);
	}
	return 0;
}