hdu3667 Hotel

  1 #include
  2 #include
  3 #include
  4 #include<string>
  5 #include
  6 #include
  7 #define rg register
  8 #define lson root << 1
  9 #define rson root << 1 | 1
 10 using namespace std;
 11 const int N = 5e4 + 10;
 12 struct node
 13 {
 14     int tag;
 15     int lsum, rsum, tsum;
 16     int len;
 17     int l, r;
 18 }t[N << 2];
 19 
 20 int n, m;
 21 
 22 inline void push_up(int root)
 23 {
 24     t[root].lsum = t[lson].lsum;
 25     t[root].rsum = t[rson].rsum;
 26     if(t[lson].lsum == t[lson].len){//如果左儿子全空，则与右儿子lsum相连 
 27         t[root].lsum += t[rson].lsum;
 28     }
 29     if(t[rson].rsum == t[rson].len){//如果右儿子全空，则与左儿子rsum相连 
 30         t[root].rsum += t[lson].rsum;
 31     }
 32     t[root].tsum = max(t[lson].rsum + t[rson].lsum, max(t[lson].tsum, t[rson].tsum));
 33     //中间段最大值更新，左端、右端、中间合并 
 34 }
 35 
 36 inline void push_down(int root)
 37 {
 38     t[lson].lsum = t[lson].rsum = t[lson].tsum = ((t[root].tag == 1) ? 0 : t[lson].len);
 39     t[rson].lsum = t[rson].rsum = t[rson].tsum = ((t[root].tag == 1) ? 0 : t[rson].len);
 40     //根据tag判断已记录的操作种类 1-check in   2-check out 
 41     t[lson].tag = t[rson].tag = t[root].tag;//tag下推
 42     t[root].tag = 0;
 43 }
 44 
 45 inline void build(int l, int r, int root)
 46 {
 47     t[root].tag = 0;
 48     t[root].l = l, t[root].r = r, t[root].len = r - l + 1;
 49     t[root].lsum = t[root].rsum = t[root].tsum = t[root].len;
 50     if(l == r)    return ;
 51     int mid = (l + r) >> 1;
 52     build(l, mid, lson);
 53     build(mid + 1, r, rson);
 54     push_up(root);
 55 }
 56 
 57 inline int query(int l, int r, int root, int x)
 58 {
 59     if(l == r && x > 1)    return 0;//找不到且已经到底 
 60     int mid = (l + r) >> 1;
 61     //左端优先级最高 左-中-右 
 62     if(t[root].lsum >= x)    return t[root].l;//自己能解决 
 63     if(t[lson].tsum >= x)    return query(l, mid, lson, x);//左儿子能解决问题
 64     if(t[lson].rsum + t[rson].lsum >= x)    return t[lson].r - t[lson].rsum + 1;//左+右共同解决 
 65     return query(mid + 1, r, rson, x);//看向右儿子 
 66 }
 67 
 68 inline void upd(int L, int R, int l, int r, int root, int id)
 69 {
 70     if(R < l || L > r)    return ;// 
 71     if(t[root].tag && l != r)    push_down(root);//下推原有tag 
 72     if(l >= L && r <= R){ 
 73         t[root].lsum = t[root].rsum = t[root].tsum = ((id == 1) ? 0 : t[root].len);//根据id修改 
 74         t[root].tag = id;
 75         return ;
 76     }
 77     int mid = (l + r) >> 1;
 78     upd(L, R, l, mid, lson, id);
 79     upd(L, R, mid + 1, r, rson, id);
 80     push_up(root);
 81 }
 82 
 83 int main(){
 84     while(~scanf("%d%d",&n,&m)){
 85         build(1, n, 1);
 86         for(rg int i = 1 ; i <= m ; i++){
 87             int id; scanf("%d",&id);
 88             if(id == 1){
 89                 int x; scanf("%d",&x);
 90                 int k = query(1, n, 1, x);//查询位置 
 91                 printf("%d\n", k);
 92                 if(k)    upd(k, k + x - 1, 1, n, 1, 1);//添加
 93             }else{
 94                 int x, y; scanf("%d%d",&x,&y);
 95                 upd(x, x + y - 1, 1, n, 1, 2);//消去
 96             }
 97         }
 98     }
 99     
100     return 0;
101 }