求助,前两个点WA了
查看原帖
求助,前两个点WA了
128870
chen_qian楼主2021/3/18 18:12
#include<bits/stdc++.h>
#define N 1500005
using namespace std;
int n,m;
struct LCT{
	int ch[N][2],fa[N],pos1[N],pos2[N],sum[N],lazy[N],val[N];
	//pos1表示最深的不为1的数
	//pos2表示最深的不为2的数 
	void push_up(int p){
		pos1[p]=pos1[ch[p][1]];
		pos2[p]=pos2[ch[p][1]];
		if(!pos1[p]){
			if(sum[p]!=1) pos1[p]=p;
			else pos1[p]=pos1[ch[p][0]];
		}
		if(!pos2[p]){
			if(sum[p]!=2) pos2[p]=p;
			else pos2[p]=pos2[ch[p][0]];
		}
	}
	void  push_tag(int p,int v){
		sum[p]+=v;
		val[p]=sum[p]>1;
		swap(pos1[p],pos2[p]);
		lazy[p]+=v;
	}
	void push_down(int p){
		if(lazy[p]){
			push_tag(ch[p][0],lazy[p]);
			push_tag(ch[p][1],lazy[p]);
			lazy[p]=0;
		}
	} 
	bool isroot(int x){
		return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
	}
	bool get(int x){
		return x==ch[fa[x]][1];
	}
	void rotate(int x){
		int y=fa[x],z=fa[y],chk=get(x);
		if(!isroot(y)) ch[z][y==ch[z][1]]=x;
		ch[y][chk]=ch[x][chk^1];
		fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y;
		fa[y]=x;
		fa[x]=z;
		push_up(y);
		push_up(x);
	}
	void update(int x){
		if(!isroot(x)) update(fa[x]);
		push_down(x);
	}
	void splay(int x){
		update(x);
		for(int f;f=fa[x],!isroot(x);rotate(x)){
			if(!isroot(f)) rotate(get(f)==get(x)?f:x);
		}
		push_up(x);
	}
	void access(int x){
		for(int p=0;x;p=x,x=fa[x]){
			splay(x);
			ch[x][1]=p;
			push_up(x);
		}
	}
}t;
int deg[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		t.fa[x]=t.fa[y]=t.fa[z]=i;
	} 
	queue<int> q;
	for(int i=n+1;i<=3*n+1;i++) scanf("%d",&t.val[i]),q.push(i),deg[t.fa[i]]=3;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		int y=t.fa[x];
		t.sum[y]+=t.val[x];
		if(!(--deg[y])){
			t.val[y]=t.sum[y]>1;
			q.push(y);
		}
	} 
	int ans=t.val[1];
	scanf("%d",&m);
	while(m--){
		int x,y;
		scanf("%d",&x);
		y=t.fa[x];
		int tag=t.val[x]?-1:1;
		t.access(y),t.splay(y);
		int flag=0;
		if(t.val[x]==1) flag=t.pos2[y];
		else flag=t.pos1[y];
		if(flag){
			t.splay(flag);
			t.push_tag(t.ch[flag][1],tag);
			t.sum[flag]+=tag;t.val[flag]=t.sum[flag]>1;t.push_up(flag);
		}
		else{
			ans^=1;
			t.push_tag(y,tag);
			t.push_up(y);
		}
		t.val[x]^=1;
		printf("%d\n",ans);
	}
	return 0;
}
/*
3
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
*/

2021/3/18 18:12
加载中...