#include <bits/stdc++.h>
using namespace std;
#define getar(ar,n) for(int i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define nl '\n'
const int mxN = 2e5 + 500;
int N=1, idx=0, parent[mxN], depth[mxN], heavy[mxN], head[mxN], sz[mxN], tin[mxN], tout[mxN], seg[mxN*4], val[mxN], till[mxN];
vector<pair<int,int>> adj[mxN];
struct Node {
Node* children[2];
Node() {
children[0] = children[1] = nullptr;
}
};
struct Trie {
Node* root;
Trie() { root = new Node(); }
void add(int x) {
Node* curr = root;
for (int i = 30; i >= 0; --i) {
int bit = (x >> i) & 1;
if (!curr->children[bit]) {
curr->children[bit] = new Node();
}
curr = curr->children[bit];
}
}
int qry(int x) {
Node* curr = root;
int ans = 0;
for (int i = 30; i >= 0; --i) {
int bit = (x >> i) & 1;
if (curr->children[1 - bit]) {
curr = curr->children[1 - bit];
ans |= (1 << i);
} else {
curr = curr->children[bit];
}
}
return ans;
}
};
unordered_map<int, Trie> t;
struct SegTree {
void update_1(int node, int start, int end, int idx, int val) {
if (start == end) {
seg[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update_1(2 * node + 1, start, mid, idx, val);
else update_1(2 * node + 2, mid + 1, end, idx, val);
seg[node] = seg[2 * node + 1] ^ seg[2 * node + 2];
}
void update_2(int node, int start, int end, int idx, int val) {
if (!t.count(node)) t[node] = Trie();
t[node].add(val);
if (start == end) return;
int mid = (start + end) / 2;
if (idx <= mid) update_2(2 * node + 1, start, mid, idx, val);
else update_2(2 * node + 2, mid + 1, end, idx, val);
}
int qry_answer(int node, int start, int end, int l, int r, int val) {
if (start > r || end < l) return 0;
if (start >= l && end <= r) return t[node].qry(val);
int mid = (start + end) / 2;
return max(qry_answer(2 * node + 1, start, mid, l, r, val), qry_answer(2 * node + 2, mid + 1, end, l, r, val));
}
int xor_qry(int node, int start, int end, int l, int r) {
if (start > r || end < l) return 0;
if (start >= l && end <= r) return seg[node];
int mid = (start + end) / 2;
return xor_qry(2 * node + 1, start, mid, l, r) ^ xor_qry(2 * node + 2, mid + 1, end, l, r);
}
} seg_tree;
struct HLD {
void dfs(int u = 1, int par = 0) {
sz[u] = 1;
parent[u] = par;
depth[u] = depth[par] + 1;
for (auto it : adj[u]) {
if (it.first != par) {
val[it.first] = it.second;
dfs(it.first, u);
sz[u] += sz[it.first];
if (sz[heavy[u]] < sz[it.first]) heavy[u] = it.first;
}
}
}
void dfsHLD(int u = 1, int chain = 1) {
head[u] = chain;
tin[u] = idx++;
seg_tree.update_1(0, 0, N - 1, tin[u], val[u]);
if (heavy[u]) dfsHLD(heavy[u], chain);
for (auto it : adj[u]) {
if (it.first != parent[u] && it.first != heavy[u]) {
dfsHLD(it.first, it.first);
}
}
tout[u] = idx - 1;
}
int path_xor(int u, int v) {
int ans = 0;
while (head[u] != head[v]) {
if (depth[head[u]] < depth[head[v]]) swap(u, v);
ans ^= seg_tree.xor_qry(0, 0, N - 1, tin[head[u]], tin[u]);
u = parent[head[u]];
}
if (depth[u] < depth[v]) swap(u, v);
return (ans ^ seg_tree.xor_qry(0, 0, N - 1, tin[v], tin[u])) ^ val[v];
}
} hld;
void lets_go() {
int q, u, v;
cin >> q;
string type;
vector<vector<int>> Q;
for (int i = 0; i < q; ++i) {
cin >> type >> u >> v;
if (type == "Add") {
Q.pb({1, u, ++N, v});
adj[u].pb({N, v});
} else {
Q.pb({0, u, v});
}
}
hld.dfs();
hld.dfsHLD();
t[0].add(0);
for (auto it : Q) {
if (it[0] == 1) {
till[it[2]] = till[it[1]] ^ it[3];
seg_tree.update_2(0, 0, N - 1, tin[it[2]], till[it[2]]);
} else {
u = it[1], v = it[2];
show(seg_tree.qry_answer(0, 0, N - 1, tin[v], tout[v], hld.path_xor(u, v) ^ till[v]));
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
lets_go();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |