CF877E Danil and a Part-time Job 题解

题目链接：CF877E Danil and a Part-time Job

题意：

一棵树有n个点，根结点编号为1，每个点的权值都是1或0
m次操作：
操作1(get)：询问一个点x的子树里有多少个1
操作2(pow)：将一个点x的子树中所有节点的权值取反
对于每一个操作1，输出答案

输入格式：
第一行一个整数n
第二行共n−1个整数，第i个数xi表示xi是i+1的父亲，
第三行给出n个点的初始权值
第四行一个整数m
接下来m行输入操作的类型和对应的节点遍号

对于每个操作1，输出1的个数

n,m<=2e5

询问&修改子树，显然需要用dfs序，然后用线段树维护

取反操作其实就是把区间和变成区间长度减区间和

而两次取反操作等于啥也没干

因此下传懒标记的时候，直接加个 \(1\) 就好了

时间复杂度 \(O(m \log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

char op[15];
int n,Q,pos=1,dfncnt;
int a[N],sum[N<<2],tag[N<<2];
int id[N],head[N],t[N],sz[N],val[N];
struct Edge{int u,v,next;}e[N];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
void push_up(int at)
{
    sum[at]=sum[ls(at)]+sum[rs(at)];
}
void build(int l,int r,int at)
{
    if(l==r){sum[at]=a[l];return;}
    int mid=(l+r)>>1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    push_up(at);
}
void proc(int l,int r,int k,int at)
{
    sum[at]=(r-l+1)-sum[at];
    tag[at]+=k;tag[at]&=1;
}
void push_down(int l,int r,int at)
{
    if(tag[at]&1)
    {
        int mid=(l+r)>>1;
        proc(l,mid,tag[at],ls(at));
        proc(mid+1,r,tag[at],rs(at));
        tag[at]=0;
    }
}
void update(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr)
    {
        sum[at]=(r-l+1)-sum[at];
        ++tag[at];tag[at]&=1;
        return;
    }
    push_down(l,r,at);
    int mid=(l+r)>>1;
    if(nl<=mid) update(nl,nr,l,mid,ls(at));
    if(nr>mid) update(nl,nr,mid+1,r,rs(at));
    push_up(at);
}
int query(int nl,int nr,int l,int r,int at)
{
    if(nl<=l&&r<=nr)
        return sum[at];
    int mid=(l+r)>>1;
    int res=0;
    push_down(l,r,at);
    if(nl<=mid)res+=query(nl,nr,l,mid,ls(at));
    if(nr>mid)res+=query(nl,nr,mid+1,r,rs(at));
    return res;
}
void dfs(int u)
{
    id[u]=++dfncnt; sz[u]=1; a[id[u]]=val[u];
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v; dfs(v);
        sz[u]+=sz[v];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=2,f; i<=n; i++)
        cin >> f,addEdge(f,i);
    for(int i=1; i<=n; i++) cin >> val[i];
    dfs(1); build(1,n,1);
    cin >> Q;
    for(int x; Q--;)
    {
        cin >> op >> x;
        if(op[0]=='p')update(id[x],id[x]+sz[x]-1,1,n,1);
        else cout << query(id[x],id[x]+sz[x]-1,1,n,1) << '\n';
    }
    return 0;
}