Codeforces 877E - Danil and a Part-time Job（dfs序＋线段树）

877E - Danil and a Part-time Job

思路：dfs序+线段树

dfs序：http://blog.csdn.net/qq_24489717/article/details/50569644

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define ls rt<<1,l,m

#define rs rt<<1|1,m+1,r

#define mem(a,b) memset(a,b,sizeof(a))

const int N=2e5+;

int tree[*N];

int lazy[*N];

int a[N];

int in[N];

int out[N];

vector<int>g[N];

void dfs(int o,int u,int &x)

{

    in[u]=x;

    for(int i=;i<g[u].size();i++)if(g[u][i]!=o)dfs(u,g[u][i],++x);

    out[u]=x;

}

void push_up(int rt)

{

    tree[rt]=tree[rt<<]+tree[rt<<|];

}

void push_down(int rt,int len)

{

    lazy[rt<<]^=lazy[rt];//对lazy数组很巧妙地运用，两次变换相当于没变

    lazy[rt<<|]^=lazy[rt];

    tree[rt<<]=(len-(len>>))-tree[rt<<];

    tree[rt<<|]=(len>>)-tree[rt<<|];

    lazy[rt]=;

}

void build(int rt,int l,int r)

{

    lazy[rt]=;

    if(l==r)

    {

        tree[rt]=a[l];

        return ;

    }

    int m=(l+r)>>;

    build(ls);

    build(rs);

    push_up(rt);

}

void Update(int L,int R,int rt,int l,int r)

{

    if(L<=l&&r<=R)

    {

        lazy[rt]^=;

        tree[rt]=r-l+-tree[rt];

        return ;

    }

    if(lazy[rt])push_down(rt,r-l+);

    int m=(l+r)>>;

    if(L<=m)Update(L,R,ls);

    if(R>m)Update(L,R,rs);

    push_up(rt);

}

int query(int L,int R,int rt,int l,int r)

{

    if(L<=l&&r<=R)return tree[rt];

    if(lazy[rt])push_down(rt,r-l+);

    int m=(l+r)>>;

    int ans=;

    if(L<=m)ans+=query(L,R,ls);

    if(R>m)ans+=query(L,R,rs);

    return ans;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,p,q,t;

    string s;

    cin>>n;

    for(int i=;i<=n;i++)

    {

        cin>>p;

        g[p].pb(i);

        g[i].pb(p);

    }

    int x=;

    dfs(,,x);

    for(int i=;i<=n;i++)cin>>a[in[i]];

    build(,,n);

    cin>>q;

    while(q--)

    {

        cin>>s>>t;

        if(s=="get")cout<<query(in[t],out[t],,,n)<<endl;

        else Update(in[t],out[t],,,n);

    }

    return ;

}