#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define fi first
#define se second
const int MAXN = 2e5 + 5;
int t, n, m, k, node = 1, val[MAXN], tin[MAXN], tout[MAXN], cnt = 0, max_dist = 0;
string s;
vector<int> adj[MAXN];
mt19937_64 rng;
struct Query{
char ch;
int x, y;
};
Query q[MAXN];
void dfs(int u){
tin[u] = ++cnt;
for(auto i: adj[u]) dfs(i);
tout[u] = cnt;
}
struct Node{
int size = 0;
vector<int> next[2];
void add(int x){
if(!size){
next[0].push_back(0);
next[1].push_back(0);
}
int crr_id = 0;
for(int i = 30; i >= 0; i--){
bool bit = (((1 << i) & x) > 0);
if(!next[bit][crr_id]){
next[0].push_back(0);
next[1].push_back(0);
next[bit][crr_id] = ++size;
}
crr_id = next[bit][crr_id];
}
}
int query(int x){
if(!size){
next[0].push_back(0);
next[1].push_back(0);
}
int crr_id = 0, ans = 0;
for(int i = 30; i >= 0; i--){
bool bit = !((1 << i) & x);
if(!next[bit][crr_id]) bit = !bit;
else ans |= (1 << i);
crr_id = next[bit][crr_id];
}
return ans;
}
};
Node st[MAXN * 4];
int get(int crr, int l, int r, int lf, int rt, int val){
if(l > rt || r < lf) return 0;
if(lf <= l && r <= rt && r - l + 1 <= max_dist) return st[crr].query(val);
int mid = l + r >> 1;
return max(get(crr * 2, l, mid, lf, rt, val), get(crr * 2 + 1, mid + 1, r, lf, rt, val));
}
void update(int crr, int l, int r, int id, int val){
if(l > id || r < id) return;
if(l == r){
if(r - l + 1 <= max_dist) st[crr].add(val);
return;
}
int mid = l + r >> 1;
update(crr * 2, l, mid, id, val);
update(crr * 2 + 1, mid + 1, r, id, val);
if(r - l + 1 <= max_dist) st[crr].add(val);
}
void solve(){
dfs(1);
node = 1;
max_dist = crr / 16;
for(int i = 1; i <= n; i++){
if(q[i].ch == 'A') node++, update(1, 1, cnt, tin[node], val[node]);
else{
int ans = get(1, 1, cnt, tin[q[i].y], tout[q[i].y], val[q[i].x]);
if(tin[q[i].y] == 1) ans = max(ans, val[q[i].x]);
cout << ans << "\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
// rng.seed((int)main ^ time(0));
#ifdef Kawaii
auto starttime = chrono::high_resolution_clock::now();
#endif
cin >> n;
for(int i = 1; i <= n; i++){
cin >> s >> q[i].x >> q[i].y;
if(s == "Add"){
q[i].ch = 'A';
val[++node] = val[q[i].x] ^ q[i].y;
adj[q[i].x].push_back(node);
}
else q[i].ch = 'Q';
}
solve();
#ifdef Kawaii
auto endtime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
cout << "\n=====" << "\nUsed: " << duration << " ms\n";
#endif
}
Compilation message
klasika.cpp: In function 'int get(int, int, int, int, int, int)':
klasika.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid = l + r >> 1;
| ~~^~~
klasika.cpp: In function 'void update(int, int, int, int, int)':
klasika.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = l + r >> 1;
| ~~^~~
klasika.cpp: In function 'void solve()':
klasika.cpp:85:16: error: 'crr' was not declared in this scope
85 | max_dist = crr / 16;
| ^~~
