学步园

题意：抗日时期，八路军擅用地道把村落连起来，现指挥官要知道一些信息：对地道的操作如下
D x  表示销毁x这个地道
Q x 表示查询有多少个地道与x相连
R   修复最后被摧毁的地道

思路：线段路，记录每个结点左边 中间，右边 连续的地道数量。

//3412K   
266MS

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

struct data
{
    int
l,r,state;   //state
-1表示空，1表示全被destroy
    int
lma,mma,rma; //左中右连续的数量
}node[3*M];
int D[M];

void BuildTree(int left ,int right,int u)
{
    node[u].l =
left;
    node[u].r =
right;
    if (left ==
right)
       
return ;
    int mid =
(left + right)>>1;
   
BuildTree(left,mid,L(u));
   
BuildTree(mid+1,right,R(u));
}
void getdown(int u,int op)
{
   
node[u].state = 0;
    if (op ==
-1)
    {
       
node[L(u)].state = -1;
       
node[L(u)].lma = node[L(u)].mma = node[L(u)].rma = node[L(u)].r -
node[L(u)].l + 1;
       
node[R(u)].state = -1;
       
node[R(u)].lma = node[R(u)].mma = node[R(u)].rma = node[R(u)].r -
node[R(u)].l + 1;
    }
    else if (op
== 1)
    {
       
node[L(u)].state = 1;
       
node[L(u)].lma = node[L(u)].mma = node[L(u)].rma = 0;
       
node[R(u)].state = 1;
       
node[R(u)].lma = node[R(u)].mma = node[R(u)].rma = 0;
    }
}
void Union (int u)
{
    if
(node[L(u)].state == -1)
       
node[u].lma = (node[L(u)].r - node[L(u)].l + 1) +
node[R(u)].lma;
    else
       
node[u].lma = node[L(u)].lma;
    if
(node[R(u)].state == -1)
       
node[u].rma = (node[R(u)].r - node[R(u)].l + 1) +
node[L(u)].rma;
    else
       
node[u].rma = node[R(u)].rma;
    node[u].mma
= node[L(u)].rma + node[R(u)].lma; //

}
void destroy (int num,int u)  //销毁操作
{
    if
(node[u].state == 1)
       
return ;
    if
(node[u].l == num&&node[u].r ==
num)  //找到点修改它的值
    {
       
node[u].state = 1;
       
node[u].lma = node[u].rma = node[u].mma = 0;
       
return ;
    }
    if
(node[u].state == -1)  //延迟覆盖
       
getdown(u,-1);
    if (num
<= node[L(u)].r)
       
destroy(num,L(u));
    if (num
>= node[R(u)].l)
       
destroy(num,R(u));
    Union
(u);          
//根据左右结点，修改父结点
    if
(node[L(u)].state == node[R(u)].state)