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
這是一個(gè)線段樹的題目：
1. 題意建模：
關(guān)鍵點(diǎn)：找出最靠左的一個(gè)長(zhǎng)度至少為K的線段可以用線段樹來做。
對(duì)任意一個(gè)線段樹中的節(jié)點(diǎn)(x,y)
維護(hù)3個(gè)信息：
1. (x, y) 中最長(zhǎng)的線段的長(zhǎng)度
2. x點(diǎn)開始向右的線段長(zhǎng)度
3. y點(diǎn)開始向左的線段長(zhǎng)度
題目要求我們對(duì)一個(gè)(0,
50000)長(zhǎng)的區(qū)間做以下操作：
A. 對(duì)任意區(qū)間 (x, y) 使 F(x,
y) = 0
B. 對(duì)任意區(qū)間 (x, y) 使 F(x,
y) = 1
C. 查詢?nèi)我庖粋€(gè)區(qū)間 (x, y) 中最長(zhǎng)的線段的長(zhǎng)度，
D. 維護(hù)每個(gè)節(jié)點(diǎn)的3種信息
2.難點(diǎn)解析：
1.實(shí)現(xiàn)A, B 操作：
要把某個(gè)節(jié)點(diǎn)覆蓋為0，或者1，不需要向下擴(kuò)展。只有在需要查詢到兒子區(qū)間的狀態(tài)的時(shí)候才需要擴(kuò)展（參考spread函數(shù)）
2.實(shí)現(xiàn)D的維護(hù)：
每次改變了左右兒子區(qū)間的信息的時(shí)候，就需要更新當(dāng)前節(jié)點(diǎn)的信息(參考update函數(shù))
3.代碼實(shí)現(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;
}