fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. vector<int> e[100005];
  8. int src[100005],cnt;
  9. int lhs[100005],rhs[100005];
  10.  
  11. void dfs(int x){
  12.     lhs[x]=cnt++;
  13.     for(size_t i=0;i<e[x].size();i++)
  14.         dfs(e[x][i]);
  15.     rhs[x]=cnt;
  16. }
  17.  
  18. class SegTree{
  19. public:
  20.     int ans[262144];
  21.     int tag[262144];
  22.     void clear(){
  23.         memset(ans,0,sizeof(ans));
  24.         memset(tag,0,sizeof(tag));
  25.     }
  26.     void modify(int l, int r, int x, int y, int i){
  27.         if(l<=x && y<=r){
  28.             tag[i]^=1;
  29.             ans[i]=y-x-ans[i];
  30.             return;
  31.         }
  32.         int m=(x+y)/2,j=i*2,k=j+1;
  33.         if(l<m) modify(l,r,x,m,j);
  34.         if(m<r) modify(l,r,m,y,k);
  35.         ans[i]=ans[j]+ans[k];
  36.         if(tag[i]) ans[i]=y-x-ans[i];
  37.     }
  38.     int getsum(int l, int r, int x, int y, int i, int v){
  39.         if(l<=x && y<=r) return v?y-x-ans[i]:ans[i];
  40.         int m=(x+y)/2,j=i*2,k=j+1,ret=0;
  41.         if(l<m) ret+=getsum(l,r,x,m,j,v^tag[i]);
  42.         if(m<r) ret+=getsum(l,r,m,y,k,v^tag[i]);
  43.         return ret;
  44.     }
  45. }seg;
  46.  
  47. int main(){
  48.     int n,m,x;
  49.     while(scanf("%d%d",&n,&m)==2){
  50.         cnt=0;
  51.         seg.clear();
  52.         for(int i=2;i<=n;i++){
  53.             scanf("%d",src+i);
  54.             e[src[i]].push_back(i);
  55.         }
  56.         dfs(1);
  57.         for(int i=1;i<=n;i++) e[i].clear();
  58.         for(int i=1;i<=m;i++){
  59.             char s[10];
  60.             scanf("%s%d",s,&x);
  61.             if(*s=='o'){
  62.                 seg.modify(lhs[x],rhs[x],0,n,1);
  63.             }else{
  64.                 int ret=seg.getsum(lhs[x],rhs[x],0,n,1,0);
  65.                 printf("%d\n",ret);
  66.             }
  67.         }
  68.         puts("");
  69.     }
  70. }
  71.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VxoVvq
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!