题意

给你一个序列 c c c，多组询问在 [ l , r ] [l,r] [l,r]区间内有多少个种类的 c c c值，满足 c ⊕ a ≤ b c\oplus a \le b c⊕a≤b (异或)。

分析

使用树状数组和字典树维护。

使用一个 v e c t o r vector vector存储每一个右端点所对应的当前询问对应的 l , a , b l,a,b l,a,b，使用 v i s vis vis数组记录当前值是否出现过，使用树状数组维护前缀，答案就是 c a l ( r ) − c a l ( l − 1 ) cal(r)-cal(l-1) cal(r)−cal(l−1)。在树状数组维护过程中，使用字典树计算数量。

c ⊕ a ≤ b c\oplus a\le b c⊕a≤b

a a a	b b b	c c c
0 0 0	0 0 0	0 0 0
0 0 0	1 1 1	1 / 0 1/0 1/0( = 1 =1 =1答案增加）
1 1 1	0 0 0	1 1 1
1 1 1	1 1 1	1 / 0 1/0 1/0( = 0 =0 =0答案增加）

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], ans[N];
int vis[N], sum[N*400]; // 记录当前数上一次出现的下标，当前节点总和
int tr[N*400][2], idx; // 字典树
int rt[N]; //树状数组
struct Node{
    int l, a, b, id;
};
vector<Node> q[N]; // 询问离线
// 在now的位置将x插入，sum+=v
void insert(int &now, int v, int x){
    if(!now) now = ++idx;
    int u = now;
    for(int i = 20; ~i; i--){
        int p = x >> i & 1;
        if(!tr[u][p]) tr[u][p] = ++idx;
        u = tr[u][p];
        sum[u] += v;
    }
}
int query(int now, int a, int b){
    if(!now) return 0;
    int res = 0, u = now;
    for(int i = 20; ~i; i --){
        int p1 = a >> i & 1;
        int p2 = b >> i & 1;
        if(p2){
            if(p1) res += sum[tr[u][1]], u = tr[u][0];
            else res += sum[tr[u][0]], u = tr[u][1];
        }else{
            if(p1) u = tr[u][1];
            else u = tr[u][0];
        }
        if(!u) break;
    }
    return res + sum[u];
}
int lowbit(int x){
    return x&(-x);
}
void add(int u, int v, int x){
    for(int i = u; i <= n; i += lowbit(i)) insert(rt[i], v, x);
}
int cal(int u, int a, int b){
    int res = 0;
    for(int i = u; i > 0; i -= lowbit(i)) res += query(rt[i], a, b);
    return res;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    cin>>m;
    for(int i = 1; i <= m; i++){
        int a, b, l, r; cin>>l>>r>>a>>b;
        q[r].push_back({l, a, b, i});
    }
    for(int i = 1; i <= n; i++){
        if(vis[a[i]]) add(vis[a[i]], -1, a[i]);
        vis[a[i]] = i;
        add(i, 1, a[i]);
        for(auto it : q[i]){
            int a = it.a, b = it.b;
            ans[it.id] = cal(i, a, b) - cal(it.l-1, a, b);
        }
    }
    for(int i = 1; i <= m; i++) cout<<ans[i]<<endl;
    return 0;
}