程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3686 後序遍歷線段樹

ZOJ 3686 後序遍歷線段樹

編輯：C++入門知識

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

題意容易理解不說了。

思路：剛開始不知道怎麼把平常的樹轉化為線段二叉樹，唉……弄了幾天，自己以前的線段樹模板寫了又寫，對lazy標記自己的結構體線段樹模板不好，所以看了別人的線段樹代碼是用數組寫的，就有點暈了……然後對比了自己的線段樹模板，發現用數組做處理lazy標記比較直觀，用起來也比較爽……哈哈，然後用了一晚上弄這個線段樹模板，相當於把以前的線段樹常用的結構體給弄翻了，又理解了好久才會……呵呵……

這道題如果用圖畫一下，就會發現這棵樹每個結點會有超過兩個的子樹，但是又是邊修改邊查詢，所以肯定是用線段樹做，所以就得把這棵不平常的樹轉化為線段樹了。

如果用後序遍歷這棵樹的話，就可以得到線性區間的線性序列，然後就可以用線段樹表示了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 100005
#define MN 105
#define INF 10000007
using namespace std;
int head[MM],num,cnt,l[MM],r[MM],sum[MM*4],val[MM*4];
struct node
{
    int v,next;
}e[MM];
void add(int u,int v)
{
    e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt++;
}
void dfs(int u)
{
    l[u]=++num;
    for(int i=head[u]; i!=-1; i=e[i].next)
        dfs(e[i].v);
    r[u]=num;
}
void push_up(int i)
{
    sum[i]=sum[i<<1]+sum[i<<1|1];
}
void push_down(int i,int m) //處理lazy標記
{
    if(val[i])
    {
        val[i<<1]^=1; val[i<<1|1]^=1;
        sum[i<<1]=(m-(m>>1))-sum[i<<1]; //因為長度為奇數的線段樹左子樹多1，比如l=1,r=7,左子樹為1->4,而右子樹為5->7,故左子樹多1
        sum[i<<1|1]=(m>>1)-sum[i<<1|1];
        val[i]=0;
    }
}
void build(int i,int l,int r)
{
    val[i]=0;
    if(l==r) { sum[i]=0; return ; }
    int mid=(l+r)>>1;
    build(lson); build(rson);
    push_up(i);
}
void update(int i,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        val[i]^=1;
        sum[i]=r-l+1-sum[i]; //長度減去總值即為更新後的值，因為值只有0,1
        return ;
    }
    int mid=(l+r)>>1;
    push_down(i,r-l+1);
    if(L<=mid) update(lson,L,R);
    if(R>mid) update(rson,L,R);
    push_up(i);
}
int query(int i,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return sum[i];
    int ans=0,mid=(l+r)>>1;
    push_down(i,r-l+1);
    if(L<=mid) ans+=query(lson,L,R);
    if(R>mid) ans+=query(rson,L,R);
    return ans;
}
int main()
{
    int n,m,u;
    char s[3];
    while(~scanf("%d%d",&n,&m))
    {
        build(1,1,n);
        mem(head,-1),cnt=0,num=0;
        for(int i=2;i<=n;i++)
            sca(u),add(u,i);
        dfs(1);
        while(m--)
        {
            scanf("%s%d",s,&u);
            if(s[0]=='o') update(1,1,n,l[u],r[u]);
            else pri(query(1,1,n,l[u],r[u]));
        }
        puts("");
    }
    return 0;
}