题目大意
询问区间内满足(c xor a < b)的不同的数的个数。
解题思路
求区间不同的数可以用树状数组离线来做，求满足(c xor a < b)的数可以用字典树来做，树状数组的每一个节点开一个字典树即可。算是两种思路的结合吧。
const int maxn = 1e5+10;
const int maxm = maxn*400;
int n, m, a[maxn];
int tr[maxm][2], cnt[maxm], idx;
int c[maxn], rt[maxn], lst[maxn], ans[maxn];
struct INFO {
int l, a, b, i;
};
vector<INFO> q[maxn];
void insert(int &p, int v, int x) {
if (!p) p = ++idx;
int now = p; //不能用p往下走，因为上面是引用
for (int i = 20; i>=0; --i) {
int t = x>>i&1;
if (!tr[now][t]) tr[now][t] = ++idx;
now = tr[now][t];
cnt[now] += v;
}
}
void add(int x, int v, int y) {
while(x<=n) {
insert(rt[x], v, y);
x += x&-x;
}
}
int query(int p, int a, int b) {
int sum = 0;
for (int i = 20; i>=0; --i) {
int t1 = a>>i&1;
int t2 = b>>i&1;
/*
a b
1 1 1++ 0
0 1 0++ 1
1 0 1
0 0 0
*/
if (t2) {
if (t1) sum += cnt[tr[p][1]], p = tr[p][0];
else sum += cnt[tr[p][0]], p = tr[p][1];
}
else {
if (t1) p = tr[p][1];
else p = tr[p][0];
}
if (!p) break;
}
return sum+cnt[p];
}
int ask(int x, int a, int b) {
int sum = 0;
while(x) {
sum += query(rt[x], a, b);
x -= x&-x;
}
return sum;
}
int main() {
IOS;
cin >> n;
for (int i = 1; i<=n; ++i) cin >> a[i];
cin >> m;
for (int i = 1; i<=m; ++i) {
int l, r, c, d; cin >> l >> r >> c >> d;
q[r].push_back({l, c, d, i});
}
for (int i = 1; i<=n; ++i) {
if (lst[a[i]]) add(lst[a[i]], -1, a[i]);
add(i, 1, a[i]);
//for (int j = 1; j<=n; ++j) cout << rt[j] << endl;
lst[a[i]] = i;
for (auto v : q[i]) ans[v.i] = ask(i, v.a, v.b)-ask(v.l-1, v.a, v.b);
}
for (int i = 1; i<=m; ++i) cout << ans[i] << endl;
return 0;
}