#include <bits/stdc++.h>
using namespace std;
int a[200005], tin[200005], tout[200005], n=1, q, t;
vector<pair<int, pair<int, int> > > vec;
vector<pair<int, int> > adj[200005];
struct bin
{
bin *lc, *rc;
short int ind;
bin(int ind) : lc(0), rc(0), ind(ind) {}
};
void update(bin *b, int x)
{
if (!b->ind)
return;
if (x&(1<<(b->ind-1)))
{
if (!b->rc)
b->rc=new bin(b->ind-1);
update(b->rc, x);
}
else
{
if (!b->lc)
b->lc=new bin(b->ind-1);
update(b->lc, x);
}
}
int query(bin *b, int x)
{
if (!b->ind)
return 0;
if (x&(1<<(b->ind-1)))
{
if (b->lc)
return (1<<(b->ind-1))^query(b->lc, x);
return query(b->rc, x);
}
else
{
if (b->rc)
return (1<<(b->ind-1))^query(b->rc, x);
return query(b->lc, x);
}
}
struct node
{
node *lc, *rc;
int l, r;
//bin *b;
vector<int> *v;
node(int l, int r) : lc(0), rc(0), l(l), r(r), v(0) {}
} *root;
void build(node *i)
{
if (i->l==i->r)
return;
int mid=(i->l+i->r)/2;
build(i->lc=new node(i->l, mid));
build(i->rc=new node(mid+1, i->r));
}
void update(node *i, int x, int y)
{
//cout << "update " << i->l << ' ' << i->r << ' ' << x << ' ' << y << '\n';
//if (i->b)
// update(i->b, y);
if (!i->v)
{
i->v=new vector<int>;
i->v->push_back(y);
}
else if (i->v->size()<1000000)
i->v->push_back(y);
/*else if (i->v->size()==1000000)
{
i->b=new bin(31);
for (int u:*(i->v))
update(i->b, u);
update(i->b, y);
delete i->v;
}*/
if (i->l==i->r)
return;
int mid=(i->l+i->r)/2;
if (x<=mid)
update(i->lc, x, y);
else
update(i->rc, x, y);
}
int query(node *i, int ql, int qr, int x)
{
//cout << "query " << i->l << ' ' << i->r << ' ' << ql << ' ' << qr << ' ' << x << '\n';
if (ql<=i->l && i->r<=qr)
{
//if (i->b)
// return query(i->b, x);
if (!i->v)
return -1;
int mx=0;
for (int u:*(i->v))
mx=max(mx, x^u);
return mx;
}
int mid=(i->l+i->r)/2, mx=0;
if (i->l<=qr && ql<=mid)
mx=max(mx, query(i->lc, ql, qr, x));
if (mid<qr && ql<=i->r)
mx=max(mx, query(i->rc, ql, qr, x));
return mx;
}
void dfs(int u)
{
tin[u]=++t;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second;
a[v]=a[u]^w;
dfs(v);
}
tout[u]=t;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> q;
for (int i=0; i<q; i++)
{
string str;
int x, y;
cin >> str >> x >> y;
if (str=="Add")
{
adj[x].push_back({++n, y});
vec.push_back({1, {n, y}});
}
else
vec.push_back({0, {x, y}});
}
dfs(1);
for (int i=1; i<=n; i++)
adj[i].clear();
build(root=new node(1, n));
update(root, 1, 0);
for (int i=0; i<q; i++)
{
if (vec[i].first)
update(root, tin[vec[i].second.first], a[vec[i].second.first]);
else
cout << query(root, tin[vec[i].second.second], tout[vec[i].second.second], a[vec[i].second.first]) << '\n';
}
}
# | 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... |