ZOJ 3686 A Simple Tree Problem（树转线段树+线段树区间更新）

浅浅的花香味﹌ 2022-06-10 02:56 164阅读 0赞

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**

3 2
    1 1
    o 2
    q 1

**Sample Output**

题解：

题意：

给你一堆节点和节点的父节点，初始全部节点为1，后来又m组操作，输入o x就是将节点x的所有子节点值反转，q x就是询问节点x子节点中为1的个数

题目的难点在于将数转化为线段树，我们先按照他给的父子关系用动态数组建好一棵树，然后将计数器id置为0，用dfs从1开始向下先序遍历，每进入一个节点，id++，然后先序遍历完该节点的所有子节点，可以发现此时id就为该节点控制的所有子节点的右边界，所以刚进入该节点的时候也是该子节点的左边界，这样就获得了每个节点控制的子节点的区间，然后剩下的就是线段树的区间更新了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    vector<int>p[100005];//存i的子节点的动态数组
    int id;
    struct dev//存每个节点管理的区间左右边界
    {
        int l,r;
    }a[100005];
    void dfs(int x)//先序遍历树
    {
        a[x].l=++id;//记录左边界
        for(int i=0;i<p[x].size();i++)//遍历每一个子节点
        {
            dfs(p[x][i]);
        }
        a[x].r=id;//记录右边界
    }
    struct node//线段树部分
    {
        int l,r;
        int sum;
        int tag;//反转标记，如果tag%2==1，就是要反转，也可以写成异或
        int len()
        {
            return r-l+1;
        }
    }t[100005*4];
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].sum=0;
        t[k].tag=0;
        if(l==r)
            return;
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushup(int k)//向上更新区间
    {
        t[k].sum=t[lson].sum+t[rson].sum;
    }
    void pushdown(int k)//向下传递状态，更新子区间
    {
        if(t[k].tag%2)
        {
            t[lson].tag+=t[k].tag;
            t[lson].sum=t[lson].len()-t[lson].sum;//区间长度-当前1的个数就是反转以后1的个数
            t[rson].tag+=t[k].tag;
            t[rson].sum=t[rson].len()-t[rson].sum;
            t[k].tag=0;
        }
    }
    void update(int l,int r,int k)//日常更新
    {
        if(t[k].l==l&&t[k].r==r)
        {
            t[k].tag++;
            t[k].sum=t[k].len()-t[k].sum;
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update(l,r,lson);
        else if(l>mid)
            update(l,r,rson);
        else
        {
            update(l,mid,lson);
            update(mid+1,r,rson);
        }
        pushup(k);
    }
    int query(int l,int r,int k)//日常询问
    {
        if(t[k].l==l&&t[k].r==r)
        {
            return t[k].sum;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            return query(l,r,lson);
        else if(l>mid)
            return query(l,r,rson);
        else
        {
            return query(l,mid,lson)+query(mid+1,r,rson);
        }
    }
    int main()
    {
        int i,j,n,m,x;
        char s[10];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            for(i=1;i<=n;i++)
                p[i].clear();
            for(i=2;i<=n;i++)
            {
                scanf("%d",&x);
                p[x].push_back(i);
            }
            id=0;
            dfs(1);
            Build(1,n,1);
            for(i=0;i<m;i++)
            {
                scanf("%s%d",s,&x);
                if(s[0]=='o')
                {
                    update(a[x].l,a[x].r,1);//更新的是子节点的左右边界
                }
                else
                {
                    printf("%d\n",query(a[x].l,a[x].r,1));
                }
            }
            printf("\n");
        }
        return 0;
    }