1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1.5e6+10; #define lc(p) tr[p].ch[0] #define rc(p) tr[p].ch[1] #define fa(p) tr[p].f struct node{int ch[2],sum[3],v,f,tag;}tr[N]; bool notrt(int x){return lc(fa(x))==x||rc(fa(x))==x;} void pushup(int x){ if(tr[rc(x)].sum[1]) tr[x].sum[1]=tr[rc(x)].sum[1]; else if(tr[x].v!=1) tr[x].sum[1]=x; else tr[x].sum[1]=tr[lc(x)].sum[1]; if(tr[rc(x)].sum[2]) tr[x].sum[2]=tr[rc(x)].sum[2]; else if(tr[x].v!=2) tr[x].sum[2]=x; else tr[x].sum[2]=tr[lc(x)].sum[2]; } void pushdown(int x,int tg) { tr[x].v^=3; swap(tr[x].sum[2],tr[x].sum[1]); tr[x].tag+=tg; } void pushall(int x) { if(notrt(x))pushall(fa(x)); if(tr[x].tag)pushdown(lc(x),tr[x].tag),pushdown(rc(x),tr[x].tag),tr[x].tag=0; } void rotate(int x) { int y=fa(x),z=fa(y),k=rc(y)==x; if(notrt(y))tr[z].ch[rc(z)==y]=x;fa(x)=z; tr[y].ch[k]=tr[x].ch[k^1];fa(tr[x].ch[k^1])=y; tr[x].ch[k^1]=y;fa(y)=x; pushup(y);pushup(x); } void splay(int x) { pushall(x); while(notrt(x)) { int y=fa(x),z=fa(y); if(notrt(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y); rotate(x); } } void access(int x) { for(int y=0;x;) { splay(x); rc(x)=y; pushup(x); y=x;x=fa(x); } } int rd[N]; int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n;cin>>n; for(int i=1;i<=n;i++) { int x1,x2,x3;cin>>x1>>x2>>x3; fa(x1)=fa(x2)=fa(x3)=i;rd[i]=3; } for(int i=n+1;i<=3*n+1;i++)cin>>tr[i].v,tr[i].v<<=1; deque<int>qu;for(int i=n+1;i<=3*n+1;i++)qu.push_back(i); while(!qu.empty()) { int x=qu.front();qu.pop_front();int y=fa(x); tr[y].v+=tr[x].v>>1; rd[y]--;if(rd[y]==0)qu.push_back(y); } int ans=tr[1].v>>1; int q;cin>>q; while(q--) { int x;cin>>x;tr[x].v^=2; int tg=tr[x].v-1; x=fa(x);access(x);splay(x); int y=(tg==1)?tr[x].sum[1]:tr[x].sum[2]; if(y) { x=y;splay(x); pushdown(rc(x),tg);pushup(rc(x)); tr[x].v+=tg;pushup(x); } else pushdown(x,tg),pushup(x),ans^=1; cout<<ans<<'\n'; } return 0; }
- 1
信息
- ID
- 5218
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 29
- 已通过
- 3
- 上传者