1 条题解

  • 0
    @ 2026-1-14 19:38:58
    #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
    上传者