传送门: 洛谷 P2894 酒店 Hotel https://www.luogu.org/problemnew/show/P2894
算法分析: 询问满足条件的连续最长区间, 不能像模板一样 \(pushup\)时直接相加, 而是要对区间进行合并.\(sum\)表示区间最大空房数,\(lsum(rsum)\)表示从左 (右) 开始的最大空房数
对于每个请求, 如果 \(op=1\) , 先检查总区间最大连续空房数是否满足要求, 然后查询. 查询完毕后为空房区间打上标记
如果 \(op=2\) , 除去 \([x,x+y)\) 的标记即可
\(pushup\ \&\ pushdown\) 的处理:
\(pushup\) : \(lsum[k]\) 表示的区间 \(A\) 和 \(lsum[ls]\) 表示的区间 \(B\) 一定满足 \(B\subseteq A\) , 故 \(lsum[k]\) 先赋为 \(lsum[ls]\) ,\(rsum\) 亦然. 之后判断能否同样包含另一区间即可
\(pushdown\) : 同 \(pushup\) , 只需判断是否退房即可
- #include<iostream>
- #include<cstdio>
- #define maxN 50000
- #define mid ((l+r)>>1)
- #define ls k<<1
- #define rs k<<1 | 1
- #define in(x) x=read()
- #define g(x,val) sum[x]=lsum[x]=rsum[x]=val
- #define lson ls,l,mid
- #define rson rs,mid+1,r
- using namespace std;
- typedef int rd;
- int lsum[4*maxN+1],rsum[4*maxN+1];
- int v[4*maxN+1],sum[4*maxN+1],n,m;
- inline rd read();
- void task(),pushup(int,int,int);
- void build(int,int,int);
- int query(int,int,int,int);
- void update(int,int,int,int,int,int);
- void pushdown(int,int,int);
- int main()
- {
- in(n); in(m); build(1,1,n);
- for(int i=1;i<=m;i++) task();
- return 0;
- }
- void update(int k,int l,int r,int ql,int qr,int u)
- {
- if(ql<=l && r<=qr)
- {
- if(!u) g(k,r-l+1); else g(k,0);
- v[k]=u; return;
- }
- if(v[k]!=-1) pushdown(k,l,r);
- if(ql<=mid) update(lson,ql,qr,u);
- if(qr>mid) update(rson,ql,qr,u);
- pushup(k,l,r);
- }
- void build(int k,int l,int r)
- {
- g(k,r-l+1); v[k]=-1;
- if(l==r) return;
- build(lson); build(rson);
- }
- void pushup(int k,int l,int r)
- {
- lsum[k]=lsum[ls];
- rsum[k]=rsum[rs];
- if(lsum[k]==r-l+1-((r-l+1)>>1)) lsum[k]+=lsum[rs];
- if(rsum[k]==((r-l+1)>>1)) rsum[k]+=rsum[ls];
- sum[k]=max(sum[ls],max(sum[rs],lsum[rs]+rsum[ls]));
- }
- void pushdown(int k,int l,int r)
- {
- v[ls]=v[rs]=v[k];
- if(!v[k])
- {
- g(ls,r-l+1-((r-l+1)>>1));
- g(rs,(r-l+1)>>1);
- }
- else g(ls,0),g(rs,0);
- v[k]=-1;
- }
- int query(int k,int l,int r,int pos)
- {
- if(l==r) return l;
- if(v[k]!=-1) pushdown(k,l,r);
- if(sum[ls]>=pos) return query(lson,pos);
- else if(rsum[ls]+lsum[rs]>=pos) return mid-rsum[ls]+1;
- return query(rson,pos);
- }
- void task()
- {
- int op,x; in(op); in(x);
- if(op==1)
- if(sum[1]<x) printf("0\n");
- else
- {
- int ans=query(1,1,n,x);
- printf("%d\n",ans);
- update(1,1,n,ans,ans+x-1,1);
- }
- else update(1,1,n,x,x+read()-1,0);
- }
- inline rd read()
- {
- rd num=0,f=1;
- char ch=getchar();
- while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
- if(ch=='-') {ch=getchar(); f=-1;}
- while(ch>='0' && ch<='9')
- {
- num=num*10+ch-'0';
- ch=getchar();
- }
- return num*f;
- }
来源: http://www.bubuko.com/infodetail-2949082.html