旅馆
【问题描述】
OIEROIEROIER 们最近的旅游计划,是到长春净月潭,享受那里的湖光山色,以及明
媚的阳光。你作为整个旅游的策划者和负责人,选择在潭边的一家著名的旅馆住
宿。这个巨大的旅馆一共有 NNN (111 <=<=<= NNN <=<=<= 500005000050000)间客房,它们在同一层楼中顺次
一字排开,在任何一个房间里,只需要拉开窗帘,就能见到波光粼粼的潭面。
所有的旅游者,都是一批批地来到旅馆的服务台,希望能订到 DiDiDi (111 <=<=<= DiDiDi <=<=<= NNN)间连续的房间。服务台的接待工作也很简单:如果存在 rrr 满足编号为 rrr…rrr+DiDiDi-111
的房间均空着,他就将这一批顾客安排到这些房间入住;如果没有满足条件的 rrr,
他会道歉说没有足够的空房间,请顾客们另找一家宾馆。如果有多个满足条件的
rrr,服务员会选择其中最小的一个。
旅馆中的退房服务也是批量进行的。每一个退房请求由 222 个数字 XiXiXi、DiDiDi 描
述,表示编号为 XiXiXi…XiXiXi+DiDiDi-111 (111 <=<=<= XiXiXi <=<=<= NNN-DiDiDi+111)房间中的客人全部离开。退房前,
请求退掉的房间中的一些,甚至是所有,可能本来就无人入住。
你的工作,就是写一个程序,帮服务员为旅客安排房间。你的程序一共需要
处理 MMM (111 <=<=<= MMM <=<=<= 500005000050000)个按输入次序到来的住店或退房的请求。第一个请求到
来前,旅店中所有房间都是空闲的。
【输入格式】
从文件 hotel.inhotel.inhotel.in 中输入数据。
第 111 行: 222 个用空格隔开的整数:NNN、MMM
第 222…M+1M+1M+1 行: 第 i+1i+1i+1 描述了第 iii 个请求,如果它是一个订房请求,则用 222 个
数字 111、DiDiDi 描述,数字间用空格隔开;如果它是一个退房请求,用 333 个以空格隔
开的数字 222、XiXiXi、DiDiDi 描述。
【输出格式】
输出到文件 hotel.outhotel.outhotel.out 中。
第 111…??????行: 对于每个订房请求,输出 111 个独占 111 行的数字:如果请求能被
满足,输出满足条件的最小的 rrr;如果请求无法被满足,输出 000。
【样例输入】
101010 666
111 333
111 333
111 333
111 333
222 555 555
111 666
【样例输出】
111
444
777
000
555
【数据规模与约定】
对于 202020%的数据, 111<=NNN<=100100100,111<=MMM<=200200200
对于 100100100%的数据,111 <= NNN <= 500005000050000 ,111 <= MMM <= 500005000050000,
数据有梯度。
该题考试的时候打了并且重构一颗线段树,顺利跑过,下面让我们来分析一下:
线段树维护区间最长连续111,区间前缀最长连续111,后缀最长连续111
在查询的时候看这个区间的最长长度是否>=ddd
如果>=ddd,则先看左子树是否>=ddd,若否看跨区间的是否>=ddd,若否再找右子树
再支持一下区间赋值即可。
下面贴上我丑陋的代码:
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<ctime>using namespace std;#define N 50005#include<iostream>#define lc (p<<1)#define rc (p<<1|1)#define mid (T[p].l+T[p].r>>1)inline long long read(){long long ans=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){ans=(ans<<3)+(ans<<1)+ch-'0';ch=getchar();}return ans*w;}inline void write(long long x){if(x<0){x=-x;putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}struct Node{int l,r,ms,ls,rs,lazy;}T[N<<2];inline int max(int a,int b){return a>b?a:b;}inline void pushup(int p){T[p].ls=T[lc].ls,T[p].rs=T[rc].rs;if(T[p].ls==T[lc].r-T[lc].l+1)T[p].ls+=T[rc].ls;if(T[p].rs==T[rc].r-T[rc].l+1)T[p].rs+=T[lc].rs;T[p].ms=max(max(T[lc].ms,T[rc].ms),T[lc].rs+T[rc].ls);}inline void pushnow(int p,int v){T[p].ls=T[p].rs=T[p].ms=(1-v)*(T[p].r-T[p].l+1);T[p].lazy=v;}inline void pushdown(int p){if(T[p].lazy==-1)return;pushnow(lc,T[p].lazy);pushnow(rc,T[p].lazy);T[p].lazy=-1;}inline void build(int p,int l,int r){T[p].l=l,T[p].r=r,T[p].lazy=-1,T[p].ls=T[p].rs=T[p].ms=r-l+1;if(l==r)return;build(lc,l,mid);build(rc,mid+1,r);pushup(p);}inline void update(int p,int ql,int qr,int v){if(ql<=T[p].l&&T[p].r<=qr){pushnow(p,v);return;}pushdown(p);if(qr<=mid)update(lc,ql,qr,v);else if(ql>mid)update(rc,ql,qr,v);else{update(lc,ql,mid,v);update(rc,mid+1,qr,v);}pushup(p);}inline int query(int p,int v){if(T[p].ms<v)return 0;if(T[p].l==T[p].r)return T[p].l;pushdown(p);if(T[lc].ms>=v)return query(lc,v);if(T[lc].rs+T[rc].ls>=v)return mid-T[lc].rs+1;return query(rc,v);}int n,m;int main(){freopen("hotel.in","r",stdin);freopen("hotel.out","w",stdout);n=read(),m=read();build(1,1,n);for(int i=1;i<=m;++i){int op=read();if(op==1){int x=read(),t=query(1,x);write(t);puts("");if(t)update(1,t,t+x-1,1);}else{int x=read(),d=read();update(1,x,x+d-1,0);}}return 0;}