Blog

题目

Luogu
LOJ
Acwing

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, w[N], maxv = 0, idx;
int a[N], root[N];
struct NODE { int l, r, s[2], c; } tr[N * 20];
void pushup(int u) { tr[u].c = tr[tr[u].s[0]].c + tr[tr[u].s[1]].c; }
int build(int l, int r) {
    int v = ++idx, mid = l + r >> 1; 
    tr[v].l = l, tr[v].r = r;
    if (l == r) return v;
    tr[v].s[0] = build(l, mid);
    tr[v].s[1] = build(mid + 1, r);
    return pushup(v), v;
}
int update(int u, int x) {
    int v = ++idx, mid = tr[u].l + tr[u].r >> 1;
    tr[v] = tr[u];
    if (tr[u].l == tr[u].r) return tr[v].c++, v;
    if (x <= mid) tr[v].s[0] = update(tr[u].s[0], x);
    else tr[v].s[1] = update(tr[u].s[1], x);
    return pushup(v), v;
}
int query(int u, int v, int l, int r) {
    int k = tr[v].c - tr[u].c;
    if (r < tr[u].l || l > tr[u].r || k == 0) return 0;
    if (tr[u].l >= l && tr[u].r <= r) return k;
    int cnt = 0, mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) cnt += query(tr[u].s[0], tr[v].s[0], l, r);
    if (r > mid) cnt += query(tr[u].s[1], tr[v].s[1], l, r);
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (register int i = 1; i <= n; i++) 
        cin >> a[i], maxv = max(maxv, a[i]);
    root[0] = build(1, maxv);
    for (register int i = 1; i <= n; i++)    
        root[i] = update(root[i - 1], a[i]);
    for (register int b, x, l, r; m-- && cin >> b >> x >> l >> r; ) {
        int ans = 0;
        for (register int i = 18; i >= 0; i--) {
            int p = query(root[l - 1], root[r], ans - x, ans - x + (1 << i) - 1);
            int q = query(root[l - 1], root[r], ans - x + (1 << i), ans - x + (1 << (i + 1)) - 1);
            if (b >> i & 1 && !p) ans += (1 << i);
            if (!(b >> i & 1) && q) ans += (1 << i);
        }
        cout << (ans ^ b) << endl;
    }
    return 0;
}