最快可以跑进 800ms

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define pb push_back
#define se second
#define ll long long  // !
#define int unsigned
namespace IO {
	const int SIZ = 1 << 14;
	inline char getc() {
	    static char bf[SIZ], *begin = bf, *end = bf;
	    if (begin == end) begin = bf, end = bf + fread(bf, 1, SIZ, stdin);
	    if (begin == end) return EOF;
	    return *begin++;
	}
	char wbf[SIZ], *wend = wbf, *weoo = wbf + SIZ;
	inline void putc(char c) {
	    *wend = c, ++wend;
	    if (wend == weoo) fwrite(wbf, 1, SIZ, stdout), wend = wbf;
	}
	inline void do_flush() { fwrite(wbf, 1, wend - wbf, stdout); }
	template <typename T>
	inline void uread(T &ans) {
	    static char tmp;
	    tmp = getc(), ans = 0;
	    while (!isdigit(tmp)) tmp = getc();
	    while (isdigit(tmp)) ans = (ans << 1) + (ans << 3) + (tmp ^ 48), tmp = getc();
	}
	template <typename T>
	inline void read(T &ans) {
	    static char tmp2;
	    static bool flag;
	    tmp2 = getc(), ans = 0, flag = 0;
	    while (!isdigit(tmp2)) {
	        if (tmp2 == '-') flag = 1;
	        tmp2 = getc();
	    }
	    while (isdigit(tmp2)) ans = (ans << 1) + (ans << 3) + (tmp2 ^ 48), tmp2 = getc();
	    if (flag) ans = -ans;
	}
	template <typename T>
	inline void uwrite(T x) {
	    if (x > 9) uwrite(x / 10);
	    putc(x % 10 + '0');
	}
	template <typename T>
	inline void write(T x) {
	    if (x < 0)
	        putc('-'), uwrite(-x);
	    else
	        uwrite(x);
	}
	inline void putstr(const char str[]) {
	    for (int i = 0; str[i]; i++) putc(str[i]);
	}
	inline void readalpha(char &x) {
	    for (x = getc(); !isalpha(x); x = getc());
	}
};  // namespace IO
using namespace IO;
namespace DS {
	struct BIT {
		int w[100010];
		inline void add(int p, int x) {
			for (int i = p; i <= 100000; i += i & (-i)) w[i] += x;
		}
		inline int query(int p) {
			int res = 0;
			for (int i = p; i; i -= i & (-i)) res += w[i]; return res;
		}
		inline void clear() {
			memset(w, 0, sizeof w);
		}
	} bit;
}
using namespace DS;
//const int N = 1e5, len = 333; 
const int N = 1e5, len = 165; 
int n, q, a[100010], b[100010];
int tot, bel[100010], L[10010], R[10010], cnt[N / len + 2][N + 2], 
	rev[N / len + 2], pre[N + 2][len + 2], las[N + 2][len + 2], cnk[N + 2][len + 2];
ll res[N / len + 2][N / len + 2];
#define deb(x) cerr << #x << '=' << x << "; " 
signed main() {
	uread(n), uread(q);
	for (int i = 1; i <= n; i++) uread(a[i]);
	for (int i = 1; i <= n; i++) bel[i] = (i - 1) / len + 1;
	tot = bel[n];
	for (int i = 1; i <= tot; i++) L[i] = (i - 1) * len + 1, R[i] = min(i * len, n); 
	for (int i = 1; i <= tot; i++) {
		for (int j = L[i]; j <= R[i]; j++) cnt[i][a[j]]++;
		for (int j = 1; j <= n; j++) cnt[i][j] += cnt[i][j - 1];
		for (int j = 1; j <= n; j++) cnt[i][j] += cnt[i - 1][j];
 	}
 	// cnt ok
 	for (int i = 1; i <= tot; i++) {
 		for (int j = L[i]; j <= R[i]; j++) {
 			rev[i] += bit.query(n) - bit.query(a[j]); bit.add(a[j], 1);
		}
		for (int j = L[i]; j <= R[i]; j++) {
		    bit.add(a[j], -1);
		}
	}
 	for (int l = 1; l <= tot; l++) {
 		for (int r = l; r <= tot; r++) {
 			res[l][r] = res[l][r - 1] + rev[r];
 			for (int i = L[r]; i <= R[r]; i++) res[l][r] += L[r] - L[l] - cnt[r - 1][a[i]] + cnt[l - 1][a[i]];
		}
	}
	// res ok
	for (int i = 1; i <= tot; i++) {
		las[R[i]][1] = a[R[i]];
		for (int j = R[i] - 1; j >= L[i]; j--) {
			int l = R[i] - j;
			for (int k = 1; k <= R[i] - j; k++) {
				las[j][k] = las[j + 1][k] < a[j] ? las[j + 1][k] : 0;
				if (!las[j][k]) {
					l = k - 1; break;
				}
			}
			las[j][l + 1] = a[j];
			for (int k = l + 1; k <= R[i] - j; k++) las[j][k + 1] = las[j + 1][k];
		}
		pre[L[i]][1] = a[L[i]];
		for (int j = L[i] + 1; j <= R[i]; j++) {
			int l = j - L[i];
			for (int k = 1; k <= j - L[i]; k++) {
				pre[j][k] = pre[j - 1][k] < a[j] ? pre[j - 1][k] : 0;
				if (!pre[j][k]) {
					l = k - 1; break;
				}
			}
			pre[j][l + 1] = a[j];
			for (int k = l + 1; k <= j - L[i]; k++) pre[j][k + 1] = pre[j - 1][k];
		}
	}
	for (int i = 1; i <= tot; i++) {
		for (int j = L[i]; j <= R[i]; j++) b[j] = lower_bound(pre[R[i]] + 1, pre[R[i]] + R[i] - L[i] + 1 + 1, a[j]) - pre[R[i]];
		for (int j = L[i]; j <= R[i]; j++) {
			if (j > L[i]) {
				for (int k = 1; k <= len; k++) cnk[j][k] = cnk[j - 1][k];
			}
			for (int k = b[j]; k <= len; k++) cnk[j][k]++;
		} 
	}
	ll lst = 0;
	while (q--) {
		int l, r;
		uread(l), uread(r);
		l ^= lst, r ^= lst;
		ll ans = 0;
		if (bel[l] == bel[r]) {
			for (int i = l; i <= r; i++) {
				ans += cnk[i][len] - cnk[i][b[i]] - (l == L[bel[l]] ? 0 : cnk[l - 1][len] - cnk[l - 1][b[i]]);
			}
			uwrite(ans); lst = ans; putc('\n'); continue;
		}
		ans = res[bel[l] + 1][bel[r] - 1];
		int p = l == L[bel[l]] ? 0 : l - 1;
		for (int i = l; i <= R[bel[l]]; i++) {
		    ans += cnt[bel[r] - 1][a[i]] - cnt[bel[l]][a[i]]
    			+ cnk[i][len] - cnk[i][b[i]] - cnk[p][len] + cnk[p][b[i]];
		}
		for (int i = L[bel[r]]; i <= r; i++) {
		    ans += L[bel[r]] - 1 - R[bel[l]] - cnt[bel[r] - 1][a[i]] + cnt[bel[l]][a[i]]
    			+ cnk[i][len] - cnk[i][b[i]];
		}
		int l1 = 0, l2 = 0, lim1 = R[bel[l]] - l + 1, lim2 = r - L[bel[r]] + 1;
		for (int i = 1; i <= lim1 + lim2; i++) {
			if ((l2 != lim2 && las[l][l1 + 1] > pre[r][l2 + 1])) {
				l2++; ans += lim1 - l1;
			} else {
			    l1++;
				if (l1 == lim1) break;
			}
		}
		uwrite(ans); lst = ans; putc('\n');
	}
	do_flush();
	return 0;
}