学步园

//8184K   
563MS

#include <stdio.h>
#include <string.h>
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define M 100010

int head[M],vis[M],low[M],high[M];
int p,dep,n;

struct data
{
    int
to,next;
}edge[M];
struct tree
{
    int
l,r,pick;          
//pick 为1 表示该点有苹果
    int
sum;
}node[3*M];

void addedge(int cu ,int cv)
{
    edge[p].to =
cv;
    edge[p].next
= head[cu];
    head[cu] =
p++;
}

void dfs (int u)
{
    low[u] =
++dep;
    vis[u] =
1;
    for (int i =
head[u];i != -1;i  = edge[i].next)
       
while (!vis[edge[i].to])
           
dfs (edge[i].to);
    high[u] =
dep;
}

void BuildTree(int left,int right,int u)
{
    node[u].l =
left;
    node[u].r =
right;
    node[u].pick
=
1;     
//建树的时候就得把树的值全部初始化 因为它可能一开始就查询
    if (left ==
right)
    {
       
node[u].sum = 1;
       
return ;
    }
    int mid =
(left + right)>>1;
   
BuildTree(left,mid,L(u));
   
BuildTree(mid+1,right,R(u));
    node[u].sum
= node[L(u)].sum + node[R(u)].sum;
}
void getdown (int u)
{
    node[u].pick
= 0;
   
node[L(u)].pick = 1;
   
node[L(u)].sum = node[L(u)].r - node[L(u)].l + 1;
   
node[R(u)].pick = 1;
   
node[R(u)].sum = node[R(u)].r - node[R(u)].l + 1;
}
void updata (int num ,int u)
{
    if
(node[u].l == num&&node[u].r ==
num)
    {
       
if (node[u].pick == 1)
       
{
           
node[u].pick = 0;
           
node[u].sum = 0;
       
}
       
else
       
{
           
node[u].pick = 1;
           
node[u].sum = 1;
       
}
       
return ;
    }
    if
(node[u].pick)
       
getdown (u);
    if (num
<= node[L(u)].r)
       
updata (num,L(u));