zoj3686(线段树的区间更新)

对线段树的区间更新有了初步的了解。。。

A Simple Tree Problem

Time Limit: 3 Seconds Memory Limit: 65536 KB

Given a rooted tree, each node has a boolean (0 or 1) labeled on it. Initially, all the labels are 0.

We define this kind of operation: given a subtree, negate all its labels.

And we want to query the numbers of 1's of a subtree.

Input

Multiple test cases.

First line, two integer N and M, denoting the numbers of nodes and numbers of operations and queries.(1<=N<=100000, 1<=M<=10000)

Then a line with N-1 integers, denoting the parent of node 2..N. Root is node 1.

Then M lines, each line are in the format "o node" or "q node", denoting we want to operate or query on the subtree with root of a certain node.

Output

For each query, output an integer in a line.

Output a blank line after each test case.

Sample Input

Sample Output

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <sstream>
#include <iostream>
using namespace std;
#define INF 0x3fffffff
#define N 100100

int n,m;
struct node
{
    int to,next;
}edge[2*N];

struct node1
{
    int b,d,mid;
    int flag,sum;
}tnode[3*N];

int cnt,pre[N];
int savex[N],savey[N];
int id;

// 线段树的区间更新初步了解！

void add_edge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=pre[u];
    pre[u]=cnt++;
}

void dfs(int s,int path)
{
    int tmp;
    ++id;
    tmp=id;
    for(int p=pre[s];p!=-1;p=edge[p].next)
    {
        int v=edge[p].to;
        if(v!=path)
        {
            dfs(v,s);
        }
    }
    savex[s]=tmp;
    savey[s]=id;
}


void built(int b,int d,int s)
{
    tnode[s].b=b;
    tnode[s].d=d;
    tnode[s].mid=(b+d)/2;
    tnode[s].sum=0;
    tnode[s].flag=0;
    if(b==d) return ;
    built(b,tnode[s].mid,2*s);
    built(tnode[s].mid+1,d,2*s+1);
}

void insert(int b,int d,int s)
{
    if(tnode[s].b==b&&tnode[s].d==d)
    {
        tnode[s].flag^=1;
        tnode[s].sum=(d-b+1) - tnode[s].sum;
        return ;
    }
    if(tnode[s].flag!=0)
    {
        tnode[s].flag=0;
        tnode[2*s].flag^=1;
        tnode[2*s].sum=(tnode[2*s].d-tnode[2*s].b+1)-tnode[2*s].sum;

        tnode[2*s+1].flag^=1;
        tnode[2*s+1].sum=(tnode[2*s+1].d-tnode[2*s+1].b+1)-tnode[2*s+1].sum;
    }
    if(tnode[s].mid>=d)
        insert(b,d,2*s);
    else if(tnode[s].mid+1<=b)
        insert(b,d,2*s+1);
    else
    {
        insert(b,tnode[s].mid,2*s);
        insert(tnode[s].mid+1,d,2*s+1);
    }
    tnode[s].sum=tnode[2*s].sum+tnode[2*s+1].sum;//用up，和down就更好理解
} //这样就不需要放回了，更简单了...


int find(int b,int d,int s)
{
    if(tnode[s].b==b&&tnode[s].d==d)
    {
        return tnode[s].sum;
    }
    if(tnode[s].flag!=0)
    {
        tnode[s].flag=0;
        tnode[2*s].flag^=1;
        tnode[2*s].sum=(tnode[2*s].d-tnode[2*s].b+1)-tnode[2*s].sum;

        tnode[2*s+1].flag^=1;
        tnode[2*s+1].sum=(tnode[2*s+1].d-tnode[2*s+1].b+1)-tnode[2*s+1].sum;
    }
    if(tnode[s].mid>=d)
        return find(b,d,s*2);
    else if(tnode[s].mid+1<=b)
        return find(b,d,2*s+1);
    else return find(b,tnode[s].mid,s*2)+find(tnode[s].mid+1,d,2*s+1);
}


int main()
{
    //freopen("//home//chen//Desktop//ACM//in.text","r",stdin);
    //freopen("//home//chen//Desktop//ACM//out.text","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        id=0;
        memset(pre,-1,sizeof(pre));
        for(int i=2;i<=n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            add_edge(i,tmp);
            add_edge(tmp,i);
        }
        dfs(1,1);
        ///////////////
        built(1,n,1);
        for(int i=0;i<m;i++)
        {
            char sel;
            int tmp;
            cin>>sel;
            scanf("%d",&tmp);
            if(sel=='o')
            {
                insert(savex[tmp],savey[tmp],1);
            }
            else
            {
                printf("%d
",find(savex[tmp],savey[tmp],1));
            }
        }
        printf("
");
    }
    return 0;
}