首先，对于 \(1,2\) 操作显然可以对于当前 Trie 上的编号开一个数组记录出现次数。
考虑 \(3\) 操作。可以树上前缀和在 \(1,2\) 操作的时候把根节点到当前编号路径上全体 \(+1\) 或 \(-1\)。
那么一个节点上的答案就记录了以其为根的子树内的答案总和。
考虑如何统计严格小于。设当前枚举到第 \(k\) 位。设 \(a_k\) 表示其在二进制下的从高到低第 \(k\) 位。
- \(p_k=0,\space l_k=0\)。
此时无法判断答案，因为 \(0 \text{ xor } 0=0\)，目前无法确定后面的位，所以无法确定是否严格小于。
- \(p_k=0,\space l_k=1\)。
此时发现符合条件的数的第 \(k\) 位一定为 \(1\)，那么这一位为 \(0\) 的全都可以统计答案。
- \(p_k=1,\space l_k=0\)。
发现符合条件的数的第 \(k\) 位一定为 \(1\)，无法统计答案，理由同 1。
- \(p_k=1,\space l_k=1\)。
发现符合条件的数的第 \(k\) 位一定为 \(0\)。否则为 \(1\) 时这一位异或值就会等于 \(0\)，统计 \(1\) 的答案。
没了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, cnt = 1, val[N << 5], ch[N << 5][2];
inline void ins(int x, int v) {
int cur; val[cur = 1] += v;
for (int i = 30; ~i; --i) {
int to = (x >> i) & 1;
if (!ch[cur][to]) ch[cur][to] = ++cnt;
cur = ch[cur][to]; val[cur] += v;
}
return ;
}
inline int query(int x, int lim) {
int cur = 1, res = 0;
for (int i = 30; ~i; --i) {
int tox = (x >> i) & 1, tolim = (lim >> i) & 1;
if (tox < tolim) res += val[ch[cur][0]];
if (tox && tolim) res += val[ch[cur][1]];
if (!tox) cur = ch[cur][tolim];
else cur = ch[cur][!tolim];
}
return res;
}
inline void solve() {
int op, x, y; cin >> op >> x;
if (op < 3) ins(x, op & 1? 1 : -1);
else cin >> y, cout << query(x, y) << endl; return ;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n; while (n--) solve(); return 0;
}