题意:
给出一个具有N个点的树,现在给出两种操作:
1.get x,表示询问以x作为根的子树中,1的个数。
2.pow x,表示将以x作为根的子树全部翻转(0变1,1变0).
思路:dfs序加上一个线段树区间修改查询。
AC代码:
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
const int maxn=2e5+5;
int sum[maxn<<2],lazy[maxn<<2],a[maxn],num[maxn],lft[maxn],rght[maxn],tot;
char s[10];
vector<int>map[maxn];
void build(int k,int l,int r){
if(l==r){
sum[k]=a[num[l]];
return ;
}
int mid=(l+r)/2;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
sum[k]=sum[k*2]+sum[k*2+1];
}
void pushdown(int k,int l,int r){
if(lazy[k]){
int mid=(l+r)/2;
sum[k*2]=mid-l+1-sum[k*2];
sum[k*2+1]=r-mid-sum[k*2+1];
//sum[k]=sum[k*2]+sum[k*2+1];
lazy[k*2]^=1;
lazy[k*2+1]^=1;
lazy[k]=0;
}
}
void update(int k,int l,int r,int L,int R){
if(L<=l&&r<=R){
sum[k]=r-l+1-sum[k];
lazy[k]^=1;
return;
}
pushdown(k,l,r);
int mid=(l+r)/2;
if(mid>=L)update(k*2,l,mid,L,R);
if(mid<R)update(k*2+1,mid+1,r,L,R);
sum[k]=sum[k*2]+sum[k*2+1];
return ;
}
int query(int k,int l,int r,int L,int R){
if(L<=l&&r<=R)return sum[k];
int ans=0;
pushdown(k,l,r);
int mid=(l+r)/2;
if(mid>=L)ans+=query(k*2,l,mid,L,R);
if(mid<R)ans+=query(k*2+1,mid+1,r,L,R);
//sum[k]=sum[k*2]+sum[k*2+1];
return ans;
}
//pushdown和query的pushup可以不要,但是在update中pushdown之后需要pushup
void dfs(int k){
lft[k]=++tot;
for(int i=0;i<map[k].size();i++){
dfs(map[k][i]);
}
rght[k]=tot;
}
//每个点的left序号就是在线段树中的序号
//每个点对应的left[i]-right[i]+1就是每个点的字节点的个数(加上自己)
int main(){
int n,x;
while(cin>>n){
for(int i=1;i<=n;i++)map[i].clear();
for(int i=2;i<=n;i++){
cin>>x;
map[x].push_back(i);
}
memset(sum,0,sizeof(sum));
memset(lazy,0,sizeof(lazy));
tot=0;
dfs(1);
/*for(int i=1;i<=n;i++){
cout<<lft[i]<<' '<<rght[i]<<endl;
}*/
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
num[lft[i]]=i;
//每个点在线段树中的序号和本身不是一样的
//注意看build函数
}
build(1,1,n);
int q;
cin>>q;
for(int i=0;i<q;i++){
cin>>s>>x;
if(s[0]=='p'){
update(1,1,n,lft[x],rght[x]);
}
else cout<<query(1,1,n,lft[x],rght[x])<<endl;
}
}
return 0;
}
圆圈中的数字是每个节点的left值,每个点的right值就是每个点的子节点中left最大的那个
该图对应输入
10
1 2 3 4 2 4 1 7 8
1 1 0 1 1 0 0 0 1 1
10
pow 1
get 2
pow 2
pow 8
get 6
pow 6
pow 10
get 6
pow 8
pow 3
输出 3 0 1
(第一次看dfs序,看了好久才明白,还耽误了吴老狗睡觉的时间T^T,还是太菜了)