rt，调了两天半了，求大佬找错 qwq

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 5, S = 320;

int n, m, a[N];
int len, id[N], L[S], R[S], pre[S][S], suf[S][S], ocr[S][N], c[N], t1[N], t2[N], p1, p2;
long long l, r, mid[S][S], lst;
pair<int, int> b[N];

inline void add(int x)
{
    for (int i = x; i <= n; i += i & -i)
        c[i]++;
}

inline int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= i & -i)
        res += c[i];
    return res;
}

inline int query(int l, int r, int x, int y) // l ~ r 中 x ~ y 的出现次数
{
    return ocr[r][y] - ocr[l - 1][y] - ocr[r][x - 1] + ocr[l - 1][x - 1];
}

inline void init()
{
    len = __builtin_sqrt(n);
    for (int i = 1; i <= n; i++)
        id[i] = (i + len - 1) / len;
    for (int i = 1; i <= id[n]; i++)
        sort(b + (L[i] = R[i - 1] + 1), b + (R[i] = min(R[i - 1] + len, n)) + 1);
    for (int i = 1; i <= id[n]; i++)
    {
        memset(c, 0, sizeof c);
        for (int j = L[i]; j <= R[i]; j++)
            pre[i][j - L[i] + 1] = pre[i][j - L[i]] + j - L[i] - sum(a[j]), add(a[j]);
        memset(c, 0, sizeof c);
        for (int j = R[i]; j >= L[i]; j--)
            suf[i][R[i] - j + 1] = suf[i][R[i] - j + 2] + sum(a[j]), add(a[j]);
    }
    for (int i = 1; i <= n; i++)
    	ocr[id[i]][a[i]]++;
    for (int i = 1; i <= id[n]; i++)
        for (int j = 1; j <= n; j++)
            ocr[i][j] += ocr[i - 1][j] + ocr[i][j - 1] - ocr[i - 1][j - 1];
    for (int i = 1; i <= id[n]; i++)
        for (int j = i; j <= id[n]; j++)
        {
            mid[i][j] = mid[i][j - 1] + pre[j][R[j] - L[j] + 1];
            for (int k = L[j]; k <= R[j]; k++)
                mid[i][j] += query(i, j - 1, a[k], n);
        }
}

inline int merge()
{
    int res = 0;
    while (p1 <= t1[0] && p2 <= t2[0])
        if (t1[p1] < t2[p2])
            p1++;
        else
            res += t1[0] - p1 + 1, p2++;
    return res;
}

inline long long query()
{
    t1[0] = t2[0] = 0, p1 = p2 = 1;
    if (id[l] == id[r])
    {
        for (int i = L[id[l]]; i <= R[id[l]]; i++)
            if (b[i].second < l)
                t1[++t1[0]] = b[i].first;
            else if (b[i].second <= r)
                t2[++t2[0]] = b[i].first;
        return pre[id[l]][r - L[id[l]] + 1] - pre[id[l]][l - L[id[l]]] - merge();
    }
    long long res = suf[id[l]][R[id[l]] - l + 1] + pre[id[r]][r - L[id[r]] + 1] + mid[id[l] + 1][id[r] - 1];
    for (int i = L[id[l]]; i <= R[id[l]]; i++)
        if (b[i].second >= l)
            t1[++t1[0]] = b[i].first, res += query(id[l] + 1, id[r] - 1, 1, b[i].first);
    for (int i = L[id[r]]; i <= R[id[r]]; i++)
        if (b[i].second <= r)
            t2[++t2[0]] = b[i].first, res += query(id[l] + 1, id[r] - 1, b[i].first, n);
    return res + merge();
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = {a[i], i};
    init();
    while (m--)
        cin >> l >> r, l ^= lst, r ^= lst, cout << (lst = query()) << "\n";
    return 0;
}