#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int LG = __lg(MAXN);
struct Trie {
struct Node {
Node *ch[2];
set<int> id;
Node() {
ch[0] = ch[1] = nullptr;
}
bool check(int l,int r) {
auto it = id.lower_bound(l);
return it != id.end() && *it <= r;
}
};
Node *head = new Node();
void add(int x,int id) {
Node *cur = head;
for (int i=30;i>=0;i--) {
int c = (x >> i) & 1;
if (cur->ch[c] == nullptr) cur->ch[c] = new Node();
cur = cur->ch[c];
cur->id.insert(id);
}
}
int query(int l,int r,int x) {
return query_recur(l,r,x,head,30);
}
int query_recur(int l,int r,int x,Node *cur,int cur_b) {
if (cur_b < 0) return 0;
if ((x >> i) & 1) {
if (cur->ch[0] == nullptr || !cur->ch[0]->check(l,r))
return query_recur(l,r,x,cur->ch[1],cur_b-1);
else return (1 << cur_b) | query_recur(l,r,x,cur->ch[0],cur_b-1);
}
else {
if (cur->ch[1] == nullptr || !cur->ch[1]->check(l,r))
return query_recur(l,r,x,cur->ch[0],cur_b-1);
else return (1 << cur_b) | query_recur(l,r,x,cur->ch[1],cur_b-1);
}
}
} trie;
struct Query {
int type;
int x,y;
Query(){};
} query[MAXN+1];
vector<int> adj[MAXN+1];
int xor_p[MAXN+1];
int tin[MAXN+1],tout[MAXN+1];
int timeDFS = 0;
void dfs(int u) {
tin[u] = ++timeDFS;
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i];
dfs(v);
}
tout[u] = timeDFS;
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
int q; cin >> q;
int cnt = 1;
for (int i=1;i<=q;i++) {
string s; cin >> s >> query[i].x >> query[i].y;
if (s == "Add") {
cnt++;
adj[query[i].x].push_back(cnt);
xor_p[cnt] = xor_p[query[i].x] ^ query[i].y;
}
else {
query[i].type = 1;
}
}
dfs(1);
cnt = 1;
for (int i=1;i<=q;i++) {
if (query[i].type == 0) {
cnt++;
trie.add(xor_p[cnt],tin[cnt]);
}
else {
// cerr << query[i].y << ' ' << tin[query[i].y] << ' ' << tout[query[i].y] << '\n';
cout << trie.query(tin[query[i].y],tout[query[i].y],xor_p[query[i].x]) << '\n';
}
}
return 0;
}
Compilation message
klasika.cpp: In member function 'int Trie::query_recur(int, int, int, Trie::Node*, int)':
klasika.cpp:35:19: error: 'i' was not declared in this scope
35 | if ((x >> i) & 1) {
| ^
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
klasika.cpp: In member function 'int Trie::query_recur(int, int, int, Trie::Node*, int)':
klasika.cpp:45:5: warning: control reaches end of non-void function [-Wreturn-type]
45 | }
| ^
