ZOJ 3686 A Simple Tree Problem

/* 
    author:ray007great 
    version:1.0 
*/  
#include<cstdio>  
#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdlib>  
#include<cmath>  
#include<vector>  
#include<queue>  
using namespace std;  
typedef long long ll;  
/*  define */  
  
#define sf(a) scanf("%d",&a)  
#define sfs(a) scanf("%s",a)  
#define sfI(a) scanf("%I64d",&a)  
#define pf(a) printf("%d\n",a)  
#define pfI(a) printf("%I64d\n",a)  
#define rep(i,a,b) for(int i=(a);i<=(b);i++)  
#define repd(i,a,b) for(int i=(a);i>=(b);i--)  
#define rep1(i,a,b) for(int i=(a);i<(b);i++)  
#define clr(a) memset(a,0,sizeof(a))  
#define pfk  printf("易做图\n")  
  
/*  define */  
  
const int N = 310000;  
int clock1;  
int lleft[N],rright[N];  
int val[4*N],lazy[4*N];  
vector<int> g[N];  
void dfs(int x){  
    if(lleft[x]) return ;  
    lleft[x]=++clock1;  
    int sz=g[x].size();  
    for(int i=0;i<sz;i++) dfs(g[x][i]);  
    rright[x]=clock1;  
}  
void Up(int o){  
    val[o]=val[o<<1]+val[o<<1|1];  
}  
void Cov(int l,int r,int o){  
    val[o]=(r-l+1)-val[o];lazy[o]=!lazy[o];  
}  
void release(int l,int r,int o){  
    int m=(l+r)>>1;  
    if(lazy[o]){  
        Cov(l,m,o<<1);Cov(m+1,r,o<<1|1);  
        lazy[o]=0;  
    }  
}  
int ql,qr;//query range  
int query(int l,int r,int o){  
    if(l>=ql && r<=qr)  return val[o];  
    release(l,r,o);  
    int m=(l+r)>>1,res=0;  
    if(ql<=m) res+=query(l,m,o<<1);  
    if(m<qr) res+=query(m+1,r,o<<1|1);  
    return res;  
}  
int ul,ur;//update range  
void update(int l,int r,int o){  
    if(l>=ul && r<=ur){  
        Cov(l,r,o);return ;  
    }  
    release(l,r,o);  
    int m=(l+r)>>1;  
    if(ul<=m) update(l,m,o<<1);  
    if(m<ur) update(m+1,r,o<<1|1);  
    Up(o);  
}  
void build(int l,int r,int o){  
    clr(val);clr(lazy);  
}  
int main(){  
    int n,q,x;  
    while(~scanf("%d%d",&n,&q)){  
        clock1=0;  
        for(int i=1;i<=n;i++) g[i].clear();  
        clr(lleft);clr(rright);  
        for(int i=2;i<=n;i++){  
            scanf("%d",&x);  
            g[x].push_back(i);g[i].push_back(x);  
        }  
        dfs(1);build(1,n,1);  
        char op[10];  
        for(int i=1;i<=q;i++){  
            scanf("%s%d",op,&x);  
            if(op[0]=='q'){  
                ql=lleft[x];qr=rright[x];  
                printf("%d\n",query(1,n,1));  
            }  
            else if(op[0]=='o'){  
                ul=lleft[x];ur=rright[x];  
                update(1,n,1);  
            }  
        }  
        printf("\n");  
    }  
    return 0;  
}