参考样例,第一行输入n,m ,n代表有n个房间,编号为1—n,开始都为空房,m表示以下有m行操作,以下 每行先输入一个数 i ,表示一种操作:
若i为1,表示查询房间,再输入一个数x,表示在1–n 房间中找到长度为x的连续空房,输出连续x个房间中左端的房间号,尽量让这个房间号最小,若找不到长度为x的连续空房,输出0。
若i为2,表示退房,再输入两个数 x,y 代表 房间号 x—x+y-1 退房,即让房间为空。
线段树代码题
维护区间最左面的连续1的长度,最右边连续1的长度,以及区间内连续1最长的长度
线段树维护左边和右边是为了为父节点合并
(上传) 做铺垫
然后 就是查找的时候需要自己想想
如果当前区间的左儿子中有连续x的1,就返回左儿子的答案
如果左儿子最右边连续的与右儿子最左边连续之和大于x,就返回答案减去左儿子的大小+mid+1(满足尽量靠左)
如果还不行就查右儿子
再不行返回0
CODE:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
const int N = 100110;
int sum[N<<2],cov[N<<2];
int ls[N<<2],rs[N<<2],mx[N<<2];//全空为1
inline int pushup(int cur,int x){
sum[cur]=sum[cur<<1]+sum[cur<<1|1];
if(sum[cur<<1]==(x+1>>1)) ls[cur]=sum[cur<<1]+ls[cur<<1|1];
else ls[cur]=ls[cur<<1];
if(sum[cur<<1|1]==(x>>1)) rs[cur]=sum[cur<<1|1]+rs[cur<<1];
else rs[cur]=rs[cur<<1|1];
mx[cur]=std::max(mx[cur<<1],std::max(mx[cur<<1|1],ls[cur<<1|1]+rs[cur<<1]));
}
inline int pushdown(int cur,int x){
if(cov[cur]!=-1){
sum[cur<<1]=cov[cur]*(x+1>>1);
sum[cur<<1|1]=cov[cur]*(x>>1);
cov[cur<<1]=cov[cur];
cov[cur<<1|1]=cov[cur];
cov[cur]=-1;
if(sum[cur<<1]) mx[cur<<1]=ls[cur<<1]=rs[cur<<1]=(x+1)>>1;
else mx[cur<<1]=ls[cur<<1]=rs[cur<<1]=0;
if(sum[cur<<1|1]) mx[cur<<1|1]=ls[cur<<1|1]=rs[cur<<1|1]=x>>1;
else mx[cur<<1|1]=ls[cur<<1|1]=rs[cur<<1|1]=0;
}
}
inline int build(int l,int r,int cur){
cov[cur]=-1;
if(l==r){
sum[cur]=ls[cur]=rs[cur]=mx[cur]=1;
return 0;
}
int mid=l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
pushup(cur,r-l+1);
return 0;
}
inline int ask(int l,int r,int cur,int x){
pushdown(cur,r-l+1);
int mid=l+r>>1;
if(l==r){
if(sum[cur]==0) return 0;
return 1;
}
if(mx[cur<<1]>=x) return ask(l,mid,cur<<1,x);
if(rs[cur<<1]+ls[cur<<1|1]>=x){
return mid-rs[cur<<1]+1;
}
if(mx[cur<<1|1]>=x)return ask(mid+1,r,cur<<1|1,x);
else return 0;
}
inline int change(int l,int r,int L,int R,int cur,int x){
if(L<=l&&r<=R){
sum[cur]=rs[cur]=ls[cur]=mx[cur]=x*(r-l+1);
cov[cur]=x;
return 0;
}
pushdown(cur,r-l+1);
int mid = l+r>>1;
if(L<=mid) change(l,mid,L,R,cur<<1,x);
if(R>mid) change(mid+1,r,L,R,cur<<1|1,x);
pushup(cur,r-l+1);
return 0;
}
int n,m;
int main (){
scanf("%d %d",&n,&m);
build(1,n,1);
while(m--){
int od,l,r,x;
scanf("%d",&od);
if(od==1){
scanf("%d",&x);
int s=ask(1,n,1,x);
printf("%d\n",s);
if(s==0) continue;
change(1,n,s,s+x-1,1,0);
}
if(od==2){
scanf("%d %d",&l,&r);
change(1,n,l,l+r-1,1,1);
}
}
return 0;
}
0 条评论