本地编译错误，提交 RE 20 分

#include <bits/stdc++.h>
#define cc(x,l,r) (cnt[x][r] - cnt[x][l - 1])

using namespace std;

struct node
{
	int v, i;
	bool operator<(const node& p)
	{
		return v < p.v;
	}
}s[100005];

int n, m, sq, c, a[100005], p[100005], d[100005], block[100005], st[1005], ed[1005], pr[100005], sf[100005], cnt[1005][100005], u[100005], v[100005];
long long S[1005][1005];

namespace BIT
{
	int T[100005];
	void add(int i, int x)
	{ 
		for( ; i < 100005 ; i += i & -i)
		{
			T[i] += x;
		}
	}
	int qry(int i)
	{ 
		int s = 0; 
		for( ; i ; i -= i & -i)
		{
			s += T[i]; 
		}
		return s; 
	}
}

void init()
{
	for (int i = 1 ; i <= c ; i ++)
	{
		sort(s + st[i], s + ed[i] + 1);
	}
	for (int i = 1 ; i <= n ; i ++)
	{
		p[i] = s[i].i;
		d[i] = s[i].v;
	}
	for (int i = 1 ; i <= c ; i ++)
	{
		int pre = 0;
		for (int j = st[i] ; j <= ed[i] ; j ++)
		{
			BIT::add(a[j], 1);
			pre += BIT::qry(n) - BIT::qry(a[j]);
			pr[j] = pre;
		}
		int suf = pre;
		for (int j = st[i] ; j <= ed[i] ; j ++)
		{
			sf[j] = suf;
			BIT::add(a[j], -1);
			suf -= BIT::qry(a[j] - 1);
		}
	}
	sort(s + 1, s + 1 + n);
	for (int j = 1 ; j <= c ; j ++)
	{
		int now = st[j];
		for (int i = 1 ; i <= n ; i ++)
		{
			while (s[i].v > d[now] && now <= ed[j])
			{
				++ now;
			}
			if (s[i].i < st[j])
			{
				cnt[j][s[i].i] = now - st[j];
			}
			if (s[i].i > ed[j])
			{
				cnt[j][s[i].i] = ed[j] - now + 1;
				if(now <= ed[j] && d[now] == s[i].v)
				{
					-- cnt[j][s[i].i];
				}
			}
		}
	}
	for (int i = 1 ; i <= c ; i ++)
	{
		S[i][i] = pr[ed[i]];
	}
	for (int i = 1 ; i <= c ; i ++)
	{
		for (int j = 2 ; j <= n ; j ++)
		{
			cnt[i][j] += cnt[i][j - 1];
		}
	}
	for (int l = 2 ; l <= c ; l ++)
	{
		for (int i = 1, j = l ; j <= c ; ++ i, ++ j)
		{
			S[i][j] = S[i][j - 1] + S[i + 1][j] - S[i + 1][j - 1] + cc(j, st[i], ed[i]);
		}
	}
}

long long merge(int x, int y)
{
	int p = 1, q = 1;
	long long ret = 0;
	while (p <= x && q <= y)
	{
		if(u[p] < v[q])
		{
			++ p;
		}
		else
		{
			++ q;
			ret += x - p + 1;
		}
	}
	return ret;
}

long long qry(int l, int r)
{
	int lb = block[l], rb = block[r], x = 0, y = 0; 
	long long ret = 0;
	if(lb == rb)
	{
		for (int i = st[lb] ; i <= ed[lb] ; i ++)
		{
			if(p[i] < l)
			{
				u[++ x] = d[i];
			}
			if(l <= p[i] && p[i] <= r)
			{
				v[++ y] = d[i]; 
			}
		}
		ret = pr[r] - merge(x, y);
		if(l ^ st[lb])
		{
			ret -= pr[l - 1];
		}
		return ret;
	}
	ret += sf[l] + pr[r];
	ret += S[lb + 1][rb - 1];
	for (int i = lb + 1 ; i <= rb - 1 ; i ++)
	{
		ret += cc(i, l, ed[lb]) + cc(i, st[rb], r);
	}
	for (int i = st[lb] ; i <= ed[lb] ; i ++)
	{
		if(l <= p[i])
		{
			u[++ x] = d[i];
		}
	}
	for (int i = st[rb] ; i <= ed[rb] ; i ++)
	{
		if(p[i] <= r)
		{
			v[++ y] = d[i];
		}
	}
	ret += merge(x,y);
	return ret;
}

int main()
{
	cin >> n >> m;
	sq = sqrt(n);
	c = (n - 1) / sq + 1;
	for (int i = 1 ; i <= n ; i ++)
	{
		cin >> a[i];
		int w = i / sq + 1;
		if (!st[w])
		{
			st[w] = i;
		}
		ed[w] = i;
		block[i] = w;
		s[i] = (node){a[i], i};
	}
	init();
	long long lastans = 0;
	while (m --)
	{
		int l, r;
		cin >> l >> r;
		l ^= lastans;
		r ^= lastans;
		cout << qry(l, r) << endl;
		lastans = qry(l, r);
	}
}