#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5;
int getbit(int x, int i) {
return (x >> i) & 1;
}
struct trie {
int node;
vector <set <int>> pos;
vector <vector <int>> ptr;
trie(int n) {
node = 0;
ptr.assign(30 * n + 5, vector <int> (2, 0));
pos.resize(n + 5);
}
void add(int x, int id) {
int cur = 0;
for (int i = 29; i >= 0; i--) {
int &p = ptr[cur][getbit(x, i)];
if (!p)
p = ++node;
cur = p;
pos[cur].insert(id);
}
}
int getmax(int x, int l, int r) {
int cur = 0;
int res = 0;
for (int i = 29; i >= 0; i--) {
bool found = false;
for (int val = 1; val >= 0; val--) {
int p = ptr[cur][val ^ getbit(x, i)];
if (!p)
continue;
auto it = pos[p].lower_bound(l);
if (it == pos[p].end() || *it > r)
continue;
found = true;
cur = p;
res |= (val << i);
break;
}
if (!found)
return -1;
}
return res;
}
};
vector <int> adj[N];
pair <int, int> pir[N];
int tin[N];
int val[N];
int tout[N];
int n = 1,q,timer;
string op[N];
void dfs(int u) {
tin[u] = ++timer;
for (int v : adj[u])
dfs(v);
tout[u] = timer;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> q;
for (int i = 1; i <= q; i++)
cin >> op[i] >> pir[i].fi >> pir[i].se;
for (int i = 1; i <= q; i++) if (op[i] == "Add") {
val[++n] = val[pir[i].fi] ^ pir[i].se;
adj[pir[i].fi].push_back(n);
pir[i].fi = n;
}
dfs(1);
tree.add(val[1], tin[1]);
for (int i = 1; i <= q; i++) {
if (op[i] == "Add")
tree.add(val[pir[i].fi], tin[pir[i].fi]);
else {
int l = tin[pir[i].se];
int r = tout[pir[i].se];
cout << tree.getmax(val[pir[i].fi], l, r) << "\n";
}
}
return 0;
}
Compilation message
klasika.cpp: In function 'int main()':
klasika.cpp:92:2: error: 'tree' was not declared in this scope; did you mean 'trie'?
92 | tree.add(val[1], tin[1]);
| ^~~~
| trie
