学步园

题意：bessie 有间旅店有N个房间 每次有一组人来住宿，他们需要连续的房间 。bessie要求你帮他个忙，有以下操作
op a ：如果op == 1 表示有a个人要住宿 要求你找出a个连续的房间 起始房间的号数要求最小，如果没有返回0
op a b ：op == 2 表示从a号房起有b个人有退房 即 a到a+b-1 的房间将置空。

思路：超经典的线段树 这道题跟上一道Hotel很像，但稍微复杂点。具体见代码说明。

#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表空，0表中间态，1表满
    int
lma,rma,ma; 
//lma表左边连续的房间数，rma表示右边连续的房间数，ma表示最大的连续房间数
}node[3*M];

int max (int a,int b)
{
    return a
> b ? a : b;
}
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)  
//延迟覆盖操作
{
    if
(node[u].state == -1)
    {
       
node[u].state = 0;
       
node[L(u)].state = -1;
       
node[L(u)].lma = node[L(u)].rma = node[L(u)].ma = node[L(u)].r -
node[L(u)].l + 1;
       
node[R(u)].state = -1;
       
node[R(u)].lma = node[R(u)].rma = node[R(u)].ma = node[R(u)].r -
node[R(u)].l + 1;
    }
    else if
(node[u].state == 1)
    {
       
node[u].state = 0;
       
node[L(u)].state = 1;
       
node[L(u)].lma = node[L(u)].rma = node[L(u)].ma = 0;
       
node[R(u)].state = 1;
       
node[R(u)].lma = node[R(u)].rma = node[R(u)].ma = 0;
    }
}
int query (int len,int u)
{
    if
(node[u].lma >=
len)   //如果左连续的房间数满足要求
       
return node[u].l;
    //if
(node[u].state != 0)
  //  getdown (u);
    if
(node[L(u)].ma >= len) 
//左结点的最大连续房间数满足要求 从左搜索（因为要求房号最小）
       
return query (len,L(u));
    if
(node[L(u)].rma + node[R(u)].lma >= len) //如果中间连续的
满足要求
       
return node[L(u)].r - node[L(u)].rma + 1;
    if
(node[R(u)].ma >=
len)     
//右结点的最大连续房间数满足要求
       
return query (len,R(u));
    return
-1;
}

void Union (int
u)             
//合并操作
{
    if
(node[L(u)].state ==
-1)       
//左为空 求node[u] 的左最大连续 以下同理
       
node[u].lma = node[L(u)].ma + node[R(u)].lma;
    else
       
node[u].lma = node[L(u)].lma;
    if
(node[R(u)].state == -1)
       
node[u].rma = node[R(u)].ma + node[L(u)].rma;
    else
       
node[u].rma = node[R(u)].rma;
    int mid_n =
node[L(u)].rma + node[R(u)].lma;
    int a = max
(node[L(u)].ma,node[R(u)].ma);