POJ 3667 Hotel【線分樹区間合併+Lazy-tag】
ホテル
Time Limit: 3000 MS
メモリLimit: 65536 K
リンク:POJ 3667
Description
The cows are jurneying north to Thunder Bay in Canda to gain cultural enrichment and enjoy a vacation on the sunnyshores of Lake Superior.Bessie,ever the copetent travel agent,has named thellmoose Hotelon Fartenmelancere N (1≦ N ≤50,000)roomsall located on the same side of an extremely long hallway(all the better totee the lake,of course)
The cows and other visitors arrive ingroup of size Di (1≦ Di ≦N)and appech the front desk to check in.Each group i request sa set of Di contigous room from Canmu,the moosestaffing the counter.He assigns the m some set of consecutive room numbers r.r+Di-1 if they are available or,ifのcontigous set of rooms is available,polity suggalternate lodging.Canmu always choes the value of r to bethe smalest possible.
Visitos also depart the hotel from groupsof contigous 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 empy before the checout.
Your job is to assist Canmu by processing M (1≦ M < 50,000)checkin/chocout requests.The hotel isitially unoccupied.
Input
*Line 1:Two space-separated integers: N and M*Lines 2.. M+1:Line i＋1 contains request expresed as one of two possible formas:(a)Two space separated integers representing acheck-n request:1 and Di (b)Threespace-separated integers representing a check-out:2、 Xi,and Di
Output
*Lines 1...:For each check-inrequest,output a single line with a single integer r,the first room in thecontigous sequence of rooms to be occupied.If the request cannot besatis fied,output 0.
Sample Input
10 6
1 3
1 3
1 3
1 3
2 5
1 6
Sample Output
1
4
7
0
5
件名:
ホテルがあります.Nの連続した部屋があります.最初は誰も住んでいません.下にM回の「1」または「2」があります.操作"1 D"はD人が部屋を選びに来ると表しています.彼らは連続番号の部屋に住んでいなければなりません.この条件を満たしていないなら、「0」を出力します.そうでないと、彼らの中で一番小さい部屋番号を出力します.操作"2 X D」ホテルは部屋番号XからD部屋がクリアされるという意味です.
分析:
実は「1」を操作すると二歩と見られます.まず、[1,N]区間には長さがD連続して使われていない部屋の区間が含まれていますか?
私の方法は線分樹区間の合併です.私の他のブログ「hdu 1540/POJ 2892 Tunnel Warfare【線分樹区間合併】」でも似たようなやり方が出ています.私は負担が多すぎません.でも、このテーマはちょっと複雑です.主に一つのLazy-の思想が多くなりました.
線分樹のテーマの種類は大体四つに分けられます.シングルポイントの更新、セグメントの増減または更新、区間の合併とスキャン線
段の更新と区間の合併は全部Lazyを使う必要があります.
スキャンラインは長方形の面積と周囲の問題を求めて、離散化を使う必要があります.
この解説では、区間合併は必ずサブノードから上に向けて行われます.このような問題は最長の連続区間を求めています.主にPusshUpの場合は、息子を左右する区間を統合する必要があります.
各ノードrtに対して、管轄範囲は[l,r]であり、私は同じように各ノードに対してln,rn,mnを[l,r]においてlで始まる連続して占有されていない区間長、rで終わる連続して占有されていない区間長、及び[l,r]この区間の最大の連続して占有されていない区間長を表しています.注意してください.ここでは占用されていません.~【具体的な区間合併の説明は、「hdu 1540/POJ 2892 Tunnel Warfare【線分樹区間合併】」の解説を見てください.
このテーマは区間の更新が必要で、区間の更新が遅れています.ここの行列は更新を遅らせるために使われています. -1はマークをクリアする時の状態を表します.区間を全部占有している状態を表します.(rt)＝1は区間が空いている状態を表しています.普通は更新の状態はi種あります.
Time Limit: 3000 MS
メモリLimit: 65536 K
リンク:POJ 3667
Description
The cows are jurneying north to Thunder Bay in Canda to gain cultural enrichment and enjoy a vacation on the sunnyshores of Lake Superior.Bessie,ever the copetent travel agent,has named thellmoose Hotelon Fartenmelancere N (1≦ N ≤50,000)roomsall located on the same side of an extremely long hallway(all the better totee the lake,of course)
The cows and other visitors arrive ingroup of size Di (1≦ Di ≦N)and appech the front desk to check in.Each group i request sa set of Di contigous room from Canmu,the moosestaffing the counter.He assigns the m some set of consecutive room numbers r.r+Di-1 if they are available or,ifのcontigous set of rooms is available,polity suggalternate lodging.Canmu always choes the value of r to bethe smalest possible.
Visitos also depart the hotel from groupsof contigous 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 empy before the checout.
Your job is to assist Canmu by processing M (1≦ M < 50,000)checkin/chocout requests.The hotel isitially unoccupied.
Input
*Line 1:Two space-separated integers: N and M*Lines 2.. M+1:Line i＋1 contains request expresed as one of two possible formas:(a)Two space separated integers representing acheck-n request:1 and Di (b)Threespace-separated integers representing a check-out:2、 Xi,and Di
Output
*Lines 1...:For each check-inrequest,output a single line with a single integer r,the first room in thecontigous sequence of rooms to be occupied.If the request cannot besatis fied,output 0.
Sample Input
10 6
1 3
1 3
1 3
1 3
2 5
1 6
Sample Output
1
4
7
0
5
件名:
ホテルがあります.Nの連続した部屋があります.最初は誰も住んでいません.下にM回の「1」または「2」があります.操作"1 D"はD人が部屋を選びに来ると表しています.彼らは連続番号の部屋に住んでいなければなりません.この条件を満たしていないなら、「0」を出力します.そうでないと、彼らの中で一番小さい部屋番号を出力します.操作"2 X D」ホテルは部屋番号XからD部屋がクリアされるという意味です.
分析:
実は「1」を操作すると二歩と見られます.まず、[1,N]区間には長さがD連続して使われていない部屋の区間が含まれていますか?
私の方法は線分樹区間の合併です.私の他のブログ「hdu 1540/POJ 2892 Tunnel Warfare【線分樹区間合併】」でも似たようなやり方が出ています.私は負担が多すぎません.でも、このテーマはちょっと複雑です.主に一つのLazy-の思想が多くなりました.
線分樹のテーマの種類は大体四つに分けられます.シングルポイントの更新、セグメントの増減または更新、区間の合併とスキャン線
段の更新と区間の合併は全部Lazyを使う必要があります.
スキャンラインは長方形の面積と周囲の問題を求めて、離散化を使う必要があります.
この解説では、区間合併は必ずサブノードから上に向けて行われます.このような問題は最長の連続区間を求めています.主にPusshUpの場合は、息子を左右する区間を統合する必要があります.
各ノードrtに対して、管轄範囲は[l,r]であり、私は同じように各ノードに対してln,rn,mnを[l,r]においてlで始まる連続して占有されていない区間長、rで終わる連続して占有されていない区間長、及び[l,r]この区間の最大の連続して占有されていない区間長を表しています.注意してください.ここでは占用されていません.~【具体的な区間合併の説明は、「hdu 1540/POJ 2892 Tunnel Warfare【線分樹区間合併】」の解説を見てください.
このテーマは区間の更新が必要で、区間の更新が遅れています.ここの行列は更新を遅らせるために使われています. -1はマークをクリアする時の状態を表します.区間を全部占有している状態を表します.(rt)＝1は区間が空いている状態を表しています.普通は更新の状態はi種あります.
/****************************>>>>HEADFILES<<<<****************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
/****************************>>>>>DEFINE<<<<<*****************************/
#define fst first
#define snd second
#define root 1,N,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PB(a) push_back(a)
#define MP(a,b) make_pair(a,b)
#define CASE(T) for(scanf("%d",&T);T--;)
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef __int64 LL;
const int INF = 0x3f3f3f3f;
/****************************>>>>SEPARATOR<<<<****************************/
const int maxn = 50000 + 5;
int N, M;
struct Node
{
int ln, rn, mn;
} segtree[maxn << 2];// Have not been occupied
int tag[maxn << 2];//-1 without tag 0 FULL 1 Empty
inline void PushUp(const int& rt, const int& l, const int& r)
{
segtree[rt].ln = segtree[rt << 1].ln;
segtree[rt].rn = segtree[rt << 1 | 1].rn;
segtree[rt].mn = max(segtree[rt << 1].rn + segtree[rt << 1 | 1].ln,
max(segtree[rt << 1].mn, segtree[rt << 1 | 1].mn));
int mid = (l + r) >> 1;
if(segtree[rt << 1].mn == mid - l + 1)
segtree[rt].ln += segtree[rt << 1 | 1].ln;
if(segtree[rt << 1 | 1].mn == r - (mid + 1) + 1)
segtree[rt].rn += segtree[rt << 1].rn;
}
inline void PushDown(const int& rt, const int& l, const int& r)
{
if(tag[rt] != -1)
{
tag[rt << 1] = tag[rt << 1 | 1] = tag[rt];
int mid = (l + r) >> 1;
segtree[rt << 1].ln = segtree[rt << 1].rn = segtree[rt << 1].mn = tag[rt] * (mid - l + 1);
segtree[rt << 1 | 1].ln = segtree[rt << 1 | 1].rn = segtree[rt << 1 | 1].mn = tag[rt] * (r - (mid + 1) + 1);
tag[rt] = -1;
}
}
void Build(int l, int r, int rt)
{
segtree[rt].ln = segtree[rt].rn = segtree[rt].mn = r - l + 1;
tag[rt] = 1;
if(l == r) return ;
int mid = (l + r) >> 1;
Build(lson);
Build(rson);
}
void Update(int L, int R, const bool& isClear, int l, int r, int rt)
{
if(L <= l && r <= R)
{
if(isClear)
{
segtree[rt].ln = segtree[rt].rn = segtree[rt].mn = r - l + 1;
tag[rt] = 1;
}
else
{
segtree[rt].ln = segtree[rt].rn = segtree[rt].mn = 0;
tag[rt] = 0;
}
return;
}
PushDown(rt, l, r);
int mid = (l + r) >> 1;
if(L <= mid)
Update(L, R, isClear, lson);
if(mid < R)
Update(L, R, isClear, rson);
PushUp(rt, l, r);
}
int Query(const int& Len, int l, int r, int rt)
{
if(segtree[rt].ln >= Len) return l;
int mid = (l + r) >> 1;
if(segtree[rt << 1].mn >= Len)
return Query(Len, lson);
else if(segtree[rt << 1].rn + segtree[rt << 1 | 1].ln >= Len)
return mid - segtree[rt << 1].rn + 1;
else
return Query(Len, rson);
}
int Op, X, D, ans;
int main()
{
// FIN;
while(~scanf("%d %d", &N, &M))
{
Build(root);
while(M--)
{
scanf("%d", &Op);
if(Op & 1)
{
scanf("%d", &D);
if(segtree[1].mn < D)
{
printf("0
");
continue;
}
ans = Query(D, root);
printf("%d
", ans);
Update(ans, ans + D - 1, false, root);
}
else
{
scanf("%d %d", &X, &D);
Update(X, X + D - 1, true, root);
}
}
}
}