1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;
int n;
const int N = 30;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct Trie {
int v, ch[2];
} T[maxn * 30]; int rt = 1, top = 1;
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; }
void ins(int &i, int k, int o, int v) {
if (!i) i = ++top;
if (o == -1) return (void) (T[i].v += v);
int d = k >> o & 1; ins(T[i].ch[d], k, o - 1, v);
maintain(i);
}
int query(int i, int k1, int k2, int o) {
if (!i) return 0;
if (o == -1) return T[i].v;
int d = k1 >> o & 1, D = k2 >> o & 1;
if (D) return T[T[i].ch[d]].v + query(T[i].ch[d ^ 1], k1, k2, o - 1);
else return query(T[i].ch[d], k1, k2, o - 1);
}
inline void solve_1() {
int x; cin >> x;
ins(rt, x, N, 1);
}
inline void solve_2() {
int x; cin >> x;
ins(rt, x, N, -1);
}
inline void solve_3() {
int x, y; cin >> x >> y;
cout << query(rt, x, y - 1, N) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
int opt; cin >> opt;
switch (opt) {
case 1 : solve_1(); break;
case 2 : solve_2(); break;
case 3 : solve_3(); break;
}
}
return 0;
}
|