ZOJ 3686線分樹

構想:1つの木の構造を与えて、1つの点を変化するたびにその子の木の上の点はすべて変わって、私达は先に深く探して、各点に番号をあげて、それから各点が影響する点の番号は連続的な1段で、このように木の構造を線形に転化して、各点は1つの区間に対応します.あとは線分樹です.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    int s,e;
}p[400005];
struct nnode
{
    int l,r,c,s;
}t[800005];
int fst[400005],next[400005],node[400005],en;
int n,m;
int cnt;
void init()
{
    en=0;
    cnt=0;
    memset(fst,-1,sizeof(fst));
}
void add(int u,int v)
{
    next[en]=fst[u];
    fst[u]=en;
    node[en]=v;
    en++;
}
void build(int ll,int rr,int rot)
{
    t[rot].l=ll;
    t[rot].r=rr;
    t[rot].s=0;
    t[rot].c=0;
    if(ll==rr)
    {
        return ;
    }
    int mid=(ll+rr)/2;
    build(ll,mid,rot<<1);
    build(mid+1,rr,rot<<1|1);
}
void dfs(int u)
{
    p[u].s=++cnt;
    for(int i=fst[u];i!=-1;i=next[i])
    {
        dfs(node[i]);
    }
    p[u].e=cnt;
}
void update(int ll,int rr,int rot)
{
    if(t[rot].l==ll&&t[rot].r==rr)
    {
        t[rot].c=(t[rot].c^1);
        t[rot].s=t[rot].r-t[rot].l+1-t[rot].s;
    }
    else
    {
        if(t[rot].c==1)
        {
            t[rot<<1].c=(t[rot<<1].c^1);
            t[rot<<1].s=(t[rot<<1].r-t[rot<<1].l+1-t[rot<<1].s);
            t[rot<<1|1].c=(t[rot<<1|1].c^1);
            t[rot<<1|1].s=(t[rot<<1|1].r-t[rot<<1|1].l+1-t[rot<<1|1].s);
            t[rot].c=0;
        }
        int mid=(t[rot].l+t[rot].r)/2;
        if(rr<=mid)update(ll,rr,rot<<1);
        else if(ll>mid)update(ll,rr,rot<<1|1);
        else
        {
            update(ll,mid,rot<<1);
            update(mid+1,rr,rot<<1|1);
        }
        t[rot].s=t[rot<<1].s+t[rot<<1|1].s;
    }
}
int query(int ll,int rr,int rot)
{
    if(t[rot].l==ll&&t[rot].r==rr)return t[rot].s;
    else
    {
        if(t[rot].c==1)
        {
            t[rot<<1].c=(t[rot<<1].c^1);
            t[rot<<1].s=(t[rot<<1].r-t[rot<<1].l+1-t[rot<<1].s);
            t[rot<<1|1].c=(t[rot<<1|1].c^1);
            t[rot<<1|1].s=(t[rot<<1|1].r-t[rot<<1|1].l+1-t[rot<<1|1].s);
            t[rot].c=0;
        }
        int mid=(t[rot].l+t[rot].r)/2;
        if(rr<=mid)return query(ll,rr,rot<<1);
        else if(ll>mid)return query(ll,rr,rot<<1|1);
        else
        {
            return query(ll,mid,rot<<1)+query(mid+1,rr,rot<<1|1);
        }
    }
}
int main()
{
    int u;
    char str[10];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&u);
            add(u,i);
        }
        dfs(1);
        build(1,n,1);
        while(m--)
        {
            scanf("%s%d",str,&u);
            if(str[0]=='o')
            {
                update(p[u].s,p[u].e,1);
            }
            else if(str[0]=='q')
            {
                cout<<query(p[u].s,p[u].e,1)<<endl;
            }
        }
        cout<<endl;
    }
    return 0;
}