洛谷P2894USACO08FEBHotel题解

题意

第一行输入 n , m n,m n,m， n n n 代表有 n n n 个房间 ( 1 ≤ n ≤ 50 , 000 ) (1\leq n \leq 50,000) (1≤n≤50,000)，编号为 1 ∼ n 1 \sim n 1∼n，开始都为空房， m m m 表示以下有 m m m 行操作 ( 1 ≤ m < 50 , 000 ) (1\leq m < 50,000) (1≤m<50,000)，以下每行先输入一个数 o p op op ，表示一种操作：

若 o p op op 为 1 1 1表示查询房间，再输入一个数 x x x，表示在 1 , 2 , . . . , n 1,2,...,n 1,2,...,n 房间中找到长度为 x x x 的连续空房，输出连续 x x x 个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为 x x x 的连续空房，输出 0 0 0。若找得到，在这 x x x 个空房间中住上人。

若 $iop为 2 2 2表示退房，再输入两个数 x , y x,y x,y 代表房间号 x ∼ x + y − 1 x \sim x+y-1 x∼x+y−1 退房，即让房间为空。

你需要对每个输入 1 1 1 输出对应的答案。

思路

目标是要维护区间内最长的连续的 0 0 0的数量。典型地，我们可以维护： 1. l m a : lma: lma:区间左端最大段连续 0 0 0 2. r m a : rma: rma:右端最大连续段 0 0 0 3. m a : ma: ma:区间的最大段连续 0 0 0

对于 p u s h u p pushup pushup操作就是取左子区间的 l m a lma lma、右子区间的 r m a rma rma和左子区间的 r m a rma rma加右子区间的 l m a lma lma，给一幅图就很清晰了： 对于该区间的 l m a lma lma，按理来说是取 l s ls ls的 l m a lma lma。但是如果当 l s ls ls的 l m a lma lma占据了整个 l s ls ls、连上了 r s rs rs的 l m a lma lma，就可以拓展这一贡献；对于该区间的 r m a rma rma同样如此。

void pushup(ll u) { T[u].ma=max(max(T[ls].ma,T[rs].ma),T[ls].rma+T[rs].lma); T[u].lma=max(T[ls].lma,(T[ls].ma==T[ls].len?T[ls].ma+T[rs].lma:0ll)); T[u].rma=max(T[rs].rma,(T[rs].ma==T[rs].len?T[rs].ma+T[ls].rma:0ll)); }

对于区间的入住与退房处理，可以使用懒标记节省时间，那么下面讲标记下放 p u s h d o w n pushdown pushdown怎么处理。

懒标记 t a g tag tag， t a g = 1 tag=1 tag=1表示一段区间的入住，入住则整一段区间没有空房了，此时本区间和左右子区间的 l m a lma lma、 r m a rma rma、 m a ma ma都为 0 0 0。

t a g = 2 tag=2 tag=2表示一段区间的退房，退房则整一段区间都是空房，此时本区间和左右子区间的 l m a lma lma、 r m a rma rma、 m a ma ma都为对应区间长度。（因此为了方便，可以再维护一个子区间长度 l e n len len）

然后就是基本的标记下放，顺便把入住和退房的函数写了：

void pushdown(ll u) { if(T[u].tag) { if(T[u].tag==1) { T[ls].ma=T[ls].lma=T[ls].rma=0; T[rs].ma=T[rs].lma=T[rs].rma=0; } else { T[ls].ma=T[ls].lma=T[ls].rma=T[ls].len; T[rs].ma=T[rs].lma=T[rs].rma=T[rs].len; } T[ls].tag=T[u].tag,T[rs].tag=T[u].tag; T[u].tag=0; } } //book:预定 leave:退房 void book(ll u,ll l,ll r,ll ql,ll qr) { if(qr<l||r<ql)return; if(ql<=l&&r<=qr) { T[u].ma=T[u].lma=T[u].rma=0; T[u].tag=1; return; } pushdown(u); ll mid=(l+r)>>1; if(ql<=mid)book(ls,l,mid,ql,qr); if(qr>mid)book(rs,mid+1,r,ql,qr); pushup(u); } void leav(ll u,ll l,ll r,ll ql,ll qr) { if(qr<l||r<ql)return; if(ql<=l&&r<=qr) { T[u].ma=T[u].lma=T[u].rma=T[u].len; T[u].tag=2; return; } pushdown(u); ll mid=(l+r)>>1; if(ql<=mid)leav(ls,l,mid,ql,qr); if(qr>mid)leav(rs,mid+1,r,ql,qr); pushup(u); }

接下来是查询操作，我们要找编号最小的，能够塞得下连续 x x x个人的空房区间，向下查询需要按照编号尽量小的优先顺序分别对左子区间 l s ls ls、中间段、右子区间 r s rs rs进行查找。要注意，找的是编号尽量小而不是空余区间尽量长的。

1.如果左子区间 l s ls ls的 m a ma ma可以塞得下 x x x，那么就往左子区间找 2.如果中间段可以满足，即 l s ls ls的 r m a rma rma加 r s rs rs的 l m a lma lma可以塞得下 x x x，那么答案就是 l s ls ls的 r m a rma rma的开始处，可以直接算出来的，就是 m i d − T [ l s ] . r m a + 1 mid-T[ls].rma+1 mid−T[ls].rma+1 3.如果右子区间可以满足，与1.同理 4.剩下没有的，直接返回 0 0 0就好了

ll query(ll u,ll l,ll r,ll len) { if(l>r||T[u].ma<len)return 0; if(l==r)return l; pushdown(u); ll mid=(l+r)>>1; if(T[ls].ma>=len)return query(ls,l,mid,len); else if(T[ls].rma+T[rs].lma>=len)return mid-T[ls].rma+1; else if(T[rs].ma>=len)return query(rs,mid+1,r,len); else return 0; }

最后提醒一句，当没有满足条件的空房间区间，输出 0 0 0之后，一定要直接 c o n t i n u e continue continue，不然就会不小心把 0 0 0之后的房间填满qwq。

#include<bits/stdc++.h> using namespace std; #define ll long long #define ls u<<1 #define rs u<<1|1 const int N=5e4+9,M=20; ll n,m; struct SegT { struct node { ll lma,rma,ma;//左右端最大连续0，区间最多连续0 ll tag,len; }T[N<<2]; void pushup(ll u) { T[u].ma=max(max(T[ls].ma,T[rs].ma),T[ls].rma+T[rs].lma); T[u].lma=max(T[ls].lma,(T[ls].ma==T[ls].len?T[ls].ma+T[rs].lma:0ll)); T[u].rma=max(T[rs].rma,(T[rs].ma==T[rs].len?T[rs].ma+T[ls].rma:0ll)); } void pushdown(ll u) { if(T[u].tag) { if(T[u].tag==1) { T[ls].ma=T[ls].lma=T[ls].rma=0; T[rs].ma=T[rs].lma=T[rs].rma=0; } else { T[ls].ma=T[ls].lma=T[ls].rma=T[ls].len; T[rs].ma=T[rs].lma=T[rs].rma=T[rs].len; } T[ls].tag=T[u].tag,T[rs].tag=T[u].tag; T[u].tag=0; } } void build(ll u,ll l,ll r) { T[u].ma=T[u].lma=T[u].rma=T[u].len=r-l+1; if(l==r)return; ll mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); pushup(u); } void book(ll u,ll l,ll r,ll ql,ll qr) { if(qr<l||r<ql)return; if(ql<=l&&r<=qr) { T[u].ma=T[u].lma=T[u].rma=0; T[u].tag=1; return; } pushdown(u); ll mid=(l+r)>>1; if(ql<=mid)book(ls,l,mid,ql,qr); if(qr>mid)book(rs,mid+1,r,ql,qr); pushup(u); } void leav(ll u,ll l,ll r,ll ql,ll qr) { if(qr<l||r<ql)return; if(ql<=l&&r<=qr) { T[u].ma=T[u].lma=T[u].rma=T[u].len; T[u].tag=2; return; } pushdown(u); ll mid=(l+r)>>1; if(ql<=mid)leav(ls,l,mid,ql,qr); if(qr>mid)leav(rs,mid+1,r,ql,qr); pushup(u); } ll query(ll u,ll l,ll r,ll len) { if(l>r||T[u].ma<len)return 0; if(l==r)return l; pushdown(u); ll mid=(l+r)>>1; if(T[ls].ma>=len)return query(ls,l,mid,len); else if(T[ls].rma+T[rs].lma>=len)return mid-T[ls].rma+1; else if(T[rs].ma>=len)return query(rs,mid+1,r,len); else return 0; } }A; int main() { scanf("%lld%lld",&n,&m); A.build(1,1,n); while(m--) { ll op,l; scanf("%lld%lld",&op,&l); if(op==1) { ll st=A.query(1,1,n,l); printf("%lld\n",st); if(st)A.book(1,1,n,st,st+l-1); } else { ll r; scanf("%lld",&r); r=r+l-1; A.leav(1,1,n,l,r); } } return 0; }