Hotel
|
Time Limit: 3000MS
|
|
Memory Limit: 65536K
|
|
Total Submissions: 478
|
|
Accepted: 129
|
Description
The cows are journeying north to
in 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 Di
(1 ≤ Di ≤ N) and approach the front desk to check in. Each
group i requests a set of Di contiguous rooms from
Canmuu, the moose staffing the counter. He assigns them some set of consecutive
room numbers r..r+Di-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 Xi and Di which specify
the vacating of rooms Xi ..Xi +Di-1
(1 ≤ Xi ≤ N-Di+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 Di (b) Three space-separated integers
representing a check-out: 2, Xi, and Di
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
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
Sample Output
1
4
7
0
5
Source
USACO
2008 February Gold
這是一個線段樹的題目：
1. 題意建模：
關(guān)鍵點：找出最靠左的一個長度至少為K的線段可以用線段樹來做。
對任意一個線段樹中的節(jié)點(x,y)
維護3個信息：
1. (x, y) 中最長的線段的長度
2. x點開始向右的線段長度
3. y點開始向左的線段長度
題目要求我們對一個(0,
50000)長的區(qū)間做以下操作：
A. 對任意區(qū)間 (x, y) 使 F(x,
y) = 0
B. 對任意區(qū)間 (x, y) 使 F(x,
y) = 1
C. 查詢?nèi)我庖粋€區(qū)間 (x, y) 中最長的線段的長度，
D. 維護每個節(jié)點的3種信息
2.難點解析：
1.實現(xiàn)A, B 操作：
要把某個節(jié)點覆蓋為0，或者1，不需要向下擴展。只有在需要查詢到兒子區(qū)間的狀態(tài)的時候才需要擴展（參考spread函數(shù)）
2.實現(xiàn)D的維護：
每次改變了左右兒子區(qū)間的信息的時候，就需要更新當前節(jié)點的信息(參考update函數(shù))
3.代碼實現(xiàn)：
#include
<stdio.h>
#define Max(a, b)
((a)>(b)?(a):(b))
const int N =
50010;
struct ST {int
i,j,m,l,r,c,lc,rc;} st[2*N]; //区间宽度的2�
int up, n;
void bd(int d, int
x, int y) {
st[d].i = x, st[d].j = y, st[d].m =
(x+y)/2;
st[d].c = st[d].lc = st[d].rc = y-x;
if(x < y-1) {
st[d].l = ++up; bd(up, x, st[d].m);
st[d].r = ++up; bd(up, st[d].m, y);
}
}
void spread(int d)
{
if(st[d].c == st[d].j-st[d].i) {
int& l = st[d].l, &r =
st[d].r;
st[l].c = st[l].lc = st[l].rc =
st[l].j-st[l].i;
st[r].c = st[r].lc = st[r].rc =
st[r].j-st[r].i;
} else if(st[d].c == 0) {
int& l = st[d].l, &r =
st[d].r;
st[l].c = st[l].lc = st[l].rc = 0;
st[r].c = st[r].lc = st[r].rc = 0;
}
}
void update(int d)
{
st[d].c = Max(Max(st[st[d].l].c,
st[st[d].r].c), st[st[d].l].rc + st[st[d].r].lc);
if(st[st[d].l].c ==
st[st[d].l].j-st[st[d].l].i) {
st[d].lc = st[st[d].l].c +
st[st[d].r].lc;
} else st[d].lc = st[st[d].l].lc;
if(st[st[d].r].rc == st[st[d].r].j-st[st[d].r].i)
{
st[d].rc = st[st[d].r].rc +
st[st[d].l].rc;
} else st[d].rc = st[st[d].r].rc;
}
void Empty(int d,
int x, int y) {
if(x <= st[d].i && y >=
st[d].j) {
st[d].c = st[d].lc = st[d].rc = 0;
return;
}
spread(d);
if(x < st[d].m) Empty(st[d].l, x, y);
if(y > st[d].m) Empty(st[d].r, x, y);
update(d);
}
void Fill(int d,
int x, int y) {
if(x <= st[d].i && y >=
st[d].j) {
st[d].c = st[d].lc = st[d].rc =
st[d].j-st[d].i;
return;
}
spread(d);
if(x < st[d].m) Fill(st[d].l, x, y);
if(y > st[d].m) Fill(st[d].r, x, y);
update(d);
}
int Get(int d, int
l) {
spread(d);
if(st[d].c < l) return -1;
if(st[st[d].l].c >= l)
return Get(st[d].l, l);
else if(st[st[d].l].rc + st[st[d].r].lc
>= l) {
return st[st[d].l].j-st[st[d].l].rc;
}
return Get(st[d].r, l);
}
int main()
{
int i, nq, cmd, x, l, y;
up = 0;
scanf("%d%d", &n, &nq);
bd(0, 0, n);
while(nq--) {
scanf("%d", &cmd);
if(cmd == 1) {
scanf("%d", &l);
x = Get(0, l);
if(x != -1)
Empty(0, x, x+l);
printf("%d\n", x+1);
} else {
scanf("%d%d", &x,
&l);
Fill(0, x-1, x+l-1);
}
}
return 0;
}