前文。

我们发现前面的做法是在线的，因此搬过来。

但是这个题卡了前面的那种分块方式，只能按排名分块了，块长取 $1300$ 跑挺快。

#include<bits/stdc++.h>
using namespace std;
int n, q, a[100005], rnk[100005], rrnk[100005], kc, ks, kl[2005], kr[2005], bel[100005], lans;
vector<int> buk[2005], vec;
pair<int, int> b[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        vec.emplace_back(a[i]); 
          b[i] = {a[i], i};
          rrnk[i] = 0x3f3f3f3f;
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++)
        rnk[b[i].second] = i;
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    kc = 1200;
    ks = (n + kc - 1) / kc;
    for (int i = 1; i <= ks; i++){
        kl[i] = kr[i - 1] + 1;
        kr[i] = kl[i] + kc - 1;
    }
    kr[ks] = n;
    for (int i = 1; i <= ks; i++)
        for (int j = kl[i]; j <= kr[i]; j++)
            bel[j] = i;
    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
        buk[bel[rnk[i]]].emplace_back(i);
        rrnk[a[i]] = min(rrnk[a[i]], rnk[i]);
    }
    cin >> q;
    while (q--){
        int l, r, k;
        cin >> l >> r >> k;
        l ^= lans;
        r ^= lans;
        k ^= lans;
        k = upper_bound(vec.begin(), vec.end(), k) - vec.begin();
        int ans = 0;
        for (int j = bel[rrnk[k]] + 1; j <= ks; j++){
            auto pl = lower_bound(buk[j].begin(), buk[j].end(), l);
            auto pr = upper_bound(buk[j].begin(), buk[j].end(), r) - 1;
            ans += pr - pl + 1;
        }
        if (k > 0){
            int u = bel[rrnk[k]];
            auto pl = lower_bound(buk[u].begin(), buk[u].end(), l);
            while (pl != buk[u].end() && *pl <= r){
                ans += (a[*pl] > k);
                ++pl;
            }
        }
        lans = ans;
        cout << ans << "\n";
    }
    return 0;
}