线段树板子WA了114514求调
查看原帖
线段树板子WA了114514求调
370648
柠檬布丁吖楼主2023/2/25 18:36
//Danil and a .....
#include<bits/stdc++.h>

using namespace std;

#define ll long long

inline ll _read(){
	ll ret=0,f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(f=-f) c=getchar();
	for(;c>='0'||c<='9';c=getchar()) ret=ret*10+c-'0';
	return ret*f;
}

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int maxn=2e5+5;
struct _tree{
	ll l,r,val,size,tag;
}t[maxn*4];

int a[maxn];
struct _edge{
	ll to,ne;
}edge[maxn];

char opt[15];

ll head[maxn],tot,dfn[maxn],out[maxn],cnt,num[maxn];
ll n;

inline void add(ll x,ll y){
	edge[++tot].to=y;edge[tot].ne=head[x];head[x]=tot;
}

void dfs(ll u,ll fa){
	dfn[u]=++cnt,num[cnt]=u;
	for(ll i=head[u];i;i=edge[i].ne){
		ll v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
	}
	out[u]=cnt;
}

void build(ll p,ll l,ll r){
	t[p].l=l;t[p].r=r;
	if(l==r){
		t[p].val=a[num[l]],t[p].size=0;
		return;
	}
	
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p].val=t[p<<1].val+t[p<<1|1].val;
	t[p].size=t[p<<1].size+t[p<<1|1].size;
}

void pushdown(ll p){
	if(t[p].tag){
		t[p<<1].val=t[p<<1].size-t[p<<1].val;
		t[p<<1|1].val=t[p<<1|1].size-t[p<<1|1].val;
		t[p<<1].tag^=1,t[p<<1|1].tag^=1;
		t[p].tag=0;
	}
}

ll ask(ll p,ll l,ll r){
	if(l<=t[p].l&&r>=t[p].r){
		return t[p].val;
	}
	pushdown(p);
	ll mid=(t[p].l+t[p].r)>>1,ans=0;
	if(l<=mid) ans+=ask(p<<1,l,r);
	if(r>mid) ans+=ask(p<<1|1,l,r);
	return ans;
}

void change(ll p,ll l,ll r){
	if(l<=t[p].l&&r>=t[p].r){
		t[p].val=t[p].size-t[p].val,t[p].tag^=1;
		return;
	}
	
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change(p<<1,l,r);
	if(r>mid) change(p<<1|1,l,r);
	t[p].val=t[p<<1].val+t[p<<1|1].val;
	t[p].size=t[p<<1].size+t[p<<1|1].size;
}

signed main(void){
	
	n=read();
	ll m,x;
	for(int i=1;i<n;i++){
		x=read();
		add(x,i+1);
	}
	
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	
	dfs(1,1);build(1,1,n);cin>>m;
	
	while(m--){
		scanf("%s",&opt);
		ll x;
//		cin>>x;
		scanf("%lld",&x);
		
		if(opt[0]=='g'){
			printf("%lld\n",ask(1,dfn[x],out[x]));
		} else {
			change(1,dfn[x],out[x]);
		}
	}
	
	return 0;
}
2023/2/25 18:36
加载中...