题目大意

给一棵数，每一个节点一开始为1，有很多个更改或询问，求根节点的子树和或将单点进行修改

思路

跑一边dfs求出树的dfs序，开一个数组tot表示当前节点的值,则有tot[p]=tot[p*2]+tot[p*2+1]

#include 
#include 
#include 
#include 
using namespace std;
#define maxn 1000001
#define max(x,y) x>y?x:y
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
inline int dfs(int dep,int x)
{
    l++;
    st[dep]=l;
    for (int i=ls[dep];i;i=e[i].next)
        if (e[i].x!=x)
            dfs(e[i].x,dep);
    ed[dep]=l;
}
inline int make(int p,int l,int r)
{
    int m=(l+r)>>1;
    if (l==r)
    {
        tot[p]=1;
        return 0;
    }
    make(p<<1,l,m);
    make(p<<1|1,m+1,r);
    tot[p]=tot[p<<1]+tot[p<<1|1];
}
inline int find(int p,int l,int r,int x,int y)
{
    int m=(l+r)>>1;
    if (l==x&&r==y)
        return tot[p];
    if (m>=y) return find(p<<1,l,m,x,y);
    else if (m>1;
    if (l==r)
    {
        tot[p]^=1;
        return 0;
    }
    if (x<=m) insert(p<<1,l,m,x);
    else insert(p<<1|1,m+1,r,x);
    tot[p]=tot[p<<1]+tot[p<<1|1];
}
int main()
{
    int n=read(),m,l=0;
    for (int i=1;i>ch;
        x=read();
        if (ch[0]=='Q')
        {
            printf("%d\n",find(1,1,n,st[x],ed[x]));
        }
        else insert(1,1,n,st[x]);
    }
}