poj 3667 Hotel (线段树)

Hotel

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 9484		Accepted: 4066

Description

The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size D_i (1 ≤ D_i ≤ N) and approach the front desk to check in. Each group i requests a set of D_i contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+D_i-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters X_i and D_i which specify the vacating of rooms X_i ..X_i +D_i-1 (1 ≤ X_i ≤ N-D_i+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

Input

* Line 1: Two space-separated integers: N and M * Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and D_i(b) Three space-separated integers representing a check-out: 2, X_i, and D_i

Output

* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

Sample Input

Sample Output

Source

USACO 2008 February Gold

【题解】：

　　线段树：

struct Nod
{
int l,r;
int ml,mm,mr; //左边的空位，区间最大的空位，右边的空位
}node[N<<2];

查找的时候优先向左边查找插入；

注意各种状态的更新

详见代码

【code】：

  1 /**
  2 judge status: Accepted      exe.time:563MS
  3 exe.memory 2712K    language:C++
  4 */
  5 
  6 #include<iostream>
  7 #include<stdio.h>
  8 #include<string.h>
  9 #include<algorithm>
 10 
 11 #define N 50010
 12 
 13 #define lson p<<1
 14 #define rson p<<1|1
 15 
 16 using namespace std;
 17 
 18 struct Nod
 19 {
 20     int l,r;
 21     int ml,mm,mr;  //左边的空位，区间最大的空位，右边的空位
 22 }node[N<<2];
 23 
 24 int id;
 25 
 26 void building(int l,int r,int p)//建树
 27 {
 28     node[p].l = l;
 29     node[p].r = r;
 30     node[p].mm=node[p].mr=node[p].ml= r-l+1;
 31     if(l==r)    return;
 32     int mid = (l+r)>>1;
 33     building(l,mid,lson);
 34     building(mid+1,r,rson);
 35 }
 36 
 37 void judgeChange(int p)  //向下更新，状态延迟标记，当搜索到整个区间一样时，向下更新一层，然后进行操作
 38 {
 39     if(node[p].mm==node[p].r-node[p].l+1)
 40     {
 41         node[lson].ml=node[lson].mm=node[lson].mr=node[lson].r-node[lson].l+1;
 42         node[rson].ml=node[rson].mm=node[rson].mr=node[rson].r-node[rson].l+1;
 43     }
 44     if(node[p].mm==0)
 45     {
 46         node[lson].ml=node[lson].mm=node[lson].mr=0;
 47         node[rson].ml=node[rson].mm=node[rson].mr=0;
 48     }
 49 }
 50 
 51 void findId(int p,int val)  //查找可以开房间的起始位置
 52 {
 53     if(node[p].l==node[p].r&&val==1) //当val为1并且已经达到叶子节点，说明没有孩子了，不必再往下查找
 54     {
 55         id = node[p].l;
 56         return;
 57     }
 58     judgeChange(p);  //状态延迟标记更新
 59     if(node[p].mm>=val)  //区间最大连续>=val时
 60     {
 61         if(node[lson].mm>=val)  //优先左边搜索
 62         {
 63             findId(lson,val);
 64         }
 65         else if(node[rson].ml+node[lson].mr>=val)  //然后中间
 66         {
 67             id = node[lson].r - node[lson].mr + 1;
 68         }
 69         else if(node[rson].mm>=val)  //最后右边
 70         {
 71             findId(rson,val);
 72         }
 73     }
 74 }
 75 
 76 void Up(int p)  //向上更新状态
 77 {
 78     node[p].ml = node[lson].ml;
 79     node[p].mr = node[rson].mr;
 80     if(node[lson].ml==node[lson].r-node[lson].l+1)
 81     {
 82         node[p].ml+=node[rson].ml;
 83     }
 84     if(node[rson].mr==node[rson].r-node[rson].l+1)
 85     {
 86         node[p].mr+=node[lson].mr;
 87     }
 88     node[p].mm = max(node[lson].mm,node[rson].mm);
 89     node[p].mm = max(node[p].mm,node[lson].mr+node[rson].ml);
 90     node[p].mm = max(node[p].mm,node[p].ml);
 91     node[p].mm = max(node[p].mm,node[p].mr);
 92 }
 93 
 94 void update(int l,int r,int p,int op) //更新
 95 {
 96     if(node[p].l==l&&node[p].r==r)
 97     {
 98         if(op==1)   node[p].ml=node[p].mm=node[p].mr=0;  //执行操作1
 99         else    node[p].ml=node[p].mm=node[p].mr=r-l+1;  //执行操作2
100         return;
101     }
102     judgeChange(p);  //状态延迟标记更新
103     int mid = (node[p].l+node[p].r)>>1;
104     if(r<=mid)  update(l,r,lson,op);
105     else if(l>mid)  update(l,r,rson,op);
106     else
107     {
108         update(l,mid,lson,op);
109         update(mid+1,r,rson,op);
110     }
111     Up(p);  //由左右孩子节点向上更新ml，mm，mr值
112 }
113 
114 
115 int main()
116 {
117     int n,m;
118     scanf("%d%d",&n,&m);
119     building(1,n,1);
120     while(m--)
121     {
122         int op,a,b;
123         scanf("%d",&op);
124         if(op==1)
125         {
126             scanf("%d",&a);
127             id = 0;
128             findId(1,a);  //查找可插入位置
129             printf("%d
",id);
130             if(id)   update(id,id+a-1,1,1);   //在id位置插入a个数，即在[id,id+a-1]插入
131         }
132         else if(op==2)
133         {
134             scanf("%d%d",&a,&b);
135             update(a,a+b-1,1,2);  //在a位置删除b个数，即把在[a,a+b-1]区间清空
136         }
137     }
138     return 0;
139 }