先不说Cache，大家看一下这代码还有没有什么可以卡常的地方啊，调块长也没用。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Len = 1e5 + 5, T = 205 , SIZE = 505;
int n, m, Num[Len][SIZE][2], t, L[SIZE], R[SIZE], pos[Len], suf[SIZE][T], pre[SIZE][T];
int sizt,val[Len];
long long Ans[SIZE][SIZE];
struct node {
    int idx, val;
} a[Len];
bool cmp(node x, node y) { return x.val < y.val; }
int c[Len];
inline int lowbit(int x) { return x & (-x); }
inline void add(int x, int w) {
    while (x <= n) c[x] += w, x += lowbit(x);
}
inline int qry(int x) {
    int res = 0;
    while (x) res += c[x], x -= lowbit(x);
    return res;
}
inline int Calc(int l, int r) {
    int fr = L[l], se = L[r];
    int num = 0;
    while (fr <= R[l] && se <= R[r]) {
        if (a[fr].val < a[se].val)
            fr++;
        else
            se++, num += R[l] - fr + 1;
    }
    return num;
}
int Used[Len][2], len[2];
inline int Cal() {
    int fr = 1, se = 1;
    int res = 0;
    while (fr <= len[0] && se <= len[1]) {
        if (Used[fr][0] < Used[se][1])
            fr ++;
        else
            se ++, res += len[0] - fr + 1;
    }
    return res;
}
inline long long qry(int l, int r) {
    int LL = pos[l], RR = pos[r];
    long long res = 0;
    if(LL == RR) 
    {
    	int res = pre[LL][r - L[RR] + 1] - pre[LL][l - 1 - L[RR] + 1];
    	len[0] = len[1] = 0;
    	for(int i = L[LL] ; i <= R[LL] ; i ++)
    	{
    		if(l <= a[i].idx && a[i].idx <= r) Used[++ len[1]][1] = a[i].val;
    		else if(a[i].idx < l) Used[++ len[0]][0] = a[i].val;
		}
		return res - Cal();
	}
    res += Ans[LL + 1][RR - 1] + suf[LL][l - L[LL] + 1] + pre[RR][r - L[RR] + 1];
    for (int i = l; i <= R[LL]; i ++) res += Num[val[i]][RR - 1][0] - Num[val[i]][LL][0];
    for (int i = L[RR]; i <= r; i ++) res += Num[val[i]][RR - 1][1] - Num[val[i]][LL][1];
    len[0] = len[1] = 0;
    for (int i = L[LL]; i <= R[LL]; i++)
        if (l <= a[i].idx && a[i].idx <= r)
            Used[++ len[0]][0] = a[i].val;
    for (int i = L[RR]; i <= R[RR]; i++)
        if (l <= a[i].idx && a[i].idx <= r)
            Used[++ len[1]][1] = a[i].val;
    return res + Cal();
}
inline long long read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    } while('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
inline void write(long long x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
signed main() {
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
    n = read() , m = read();
    for (int i = 1; i <= n; i++) {
        a[i].val = read();
        a[i].idx = i;
    }
    for (int i = 1; i <= n; i++) val[i] = a[i].val;
    t = 205;
    sizt = n / t;
    for (int i = 1; i <= sizt; i++) L[i] = (i - 1) * t + 1, R[i] = i * t;
    if (R[sizt] < n) {
        sizt ++;
        L[sizt] = R[sizt - 1] + 1;
        R[sizt] = n;
    }
    for (int i = 1; i <= sizt; i++)
        for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
    /*for (int now = 1; now <= sizt; now++) {
        for (int len = 2; len <= R[now] - L[now] + 1; len++) {
            for (int i = L[now]; i + len - 1 <= R[now]; i++) {
                int j = i + len - 1;
				#define I i - L[now] + 1
				#define J j - L[now] + 1
                Anss[now][I][J] = Anss[now][I + 1][J] + Anss[now][I][J - 1] - Anss[now][I + 1][J - 1] +
                                  (a[i].val > a[j].val);
				//printf("%d\n",Anss[now][I][J]);
				#undef I
				#undef J
				
            }
        }
    }*/
    for (int i = 1; i <= sizt; i++) {
        int sim = 0;
        for (int j = L[i]; j <= R[i]; j++) {
            sim += qry(n) - qry(a[j].val);
            pre[i][j - L[i] + 1] = sim;
            add(a[j].val , 1);
        }
        for (int j = L[i]; j <= R[i]; j++) add(a[j].val, -1);
        sim = 0;
        for (int j = R[i]; j >= L[i]; j--) {
            sim += qry(a[j].val - 1);
            suf[i][j - L[i] + 1] = sim;
            add(a[j].val , 1);
        }
        for (int j = L[i]; j <= R[i]; j++) add(a[j].val, -1);
        //printf("%d\n",i);
       // for(int j = L[i] ; j <= R[i] ; j ++) printf("%d ",pre[i][j - L[i] + 1]);
        //puts("");
        //for(int j = L[i] ; j <= R[i] ; j ++) printf("%d ",suf[i][j - L[i] + 1]);
        //puts("");
        Ans[i][i] = pre[i][R[i] - L[i] + 1];
    }
    for (int i = 1; i <= sizt; i++) {
        for (int j = L[i]; j <= R[i]; j++)
            Num[val[j] + 1][i][0] ++, Num[val[j] - 1][i][1] ++;           //记录比它小的和大的
        for (int j = n ; j >= 1; j --) Num[j][i][1] += Num[j + 1][i][1];  //处理比它大的
        for (int j = 1 ; j <= n; j ++) Num[j][i][0] += Num[j - 1][i][0];  //处理比它小的
        for(int j = 1 ; j <= n ; j ++)
		{ 
			//if(j == 6 && i == 2) printf("#%d\n",Num[j][i][0]);
            Num[j][i][0] += Num[j][i - 1][0];
            Num[j][i][1] += Num[j][i - 1][1];
            //printf("%d %d %d %d\n",i,j,Num[j][i][0],Num[j][i][1]);
        }
    }
    for (int i = 1; i <= sizt; i++) sort(a + L[i], a + R[i] + 1, cmp);
    for (int len = 2; len <= sizt; len++) {
        for (int i = 1; i + len - 1 <= t; i++) {
            int j = i + len - 1;
            Ans[i][j] = Ans[i][j - 1] + Ans[i + 1][j] - Ans[i + 1][j - 1] + Calc(i , j);
            //printf("%d\n",Ans[i][j]);
        }
    }

    long long lstans = 0;
    for (int i = 1; i <= m; i++) {
        long long l, r;
        l = read() , r = read();
        l = l ^ lstans, r = r ^ lstans;
        if(l > r) swap(l , r); 
        write(lstans = qry(l , r)) , putchar('\n');
    }
    return 0;
}
/*
10 1
6 4 5 1 10 7 8 9 3 2 
1 7
*/