可持久化线段树

例题

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e5 + 9;
int n, q, a[N], b[N];
map <LL, int> ib;
struct Persistent_Segment_Tree
{
    struct Point
    {
        int l, r;
        LL sum;
    }p[N * 25];
    int rt[N], cnt = 0;
    
    void Newpoint(int &rt, int last, int l, int r, int x, int v)
    {
        rt = ++cnt;
        p[rt] = p[last], p[rt].sum += v;
        if (l == r) return;
        int mid = l + r >> 1;
        if (x <= mid) Newpoint(p[rt].l, p[last].l, l, mid, x, v);
        else Newpoint(p[rt].r, p[last].r, mid + 1, r, x, v);
    }

    LL Query(int rt_1, int rt_2, int l, int r, int x, int y)
    {
        if(x <= l && y >= r)
            return p[rt_2].sum - p[rt_1].sum;
        LL res = 0;
        int mid = l + r >> 1;
        if (x <= mid)
            res += Query(p[rt_1].l, p[rt_2].l, l, mid, x, y);
        if (y >= mid + 1)
            res += Query(p[rt_1].r, p[rt_2].r, mid + 1, r, x, y);
        return res;
    }
}PT;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - (b + 1);
    for (int i = 1; i <= len; i++)
        ib[b[i]] = i;
    for (int i = 1; i <= n; i++)
        PT.Newpoint(PT.rt[i], PT.rt[i - 1], 1, len, ib[a[i]], a[i]);
    scanf("%d", &q);
    LL last = 0;
    while (q--)
    {
        LL l, r, x;
        cin >> l >> r >> x;
        l ^= last, r ^= last, x ^= last;
        int pos = upper_bound(b + 1, b + 1 + len, x) - (b + 1);
        if (pos)
            last = PT.Query(PT.rt[l - 1], PT.rt[r], 1, len, 1, ib[b[pos]]);
        else
            last = 0;
        cout << last << endl;
    }
    return 0;
}