//POJ 3667 Hotel 线段树 区间合并(成段更新)
/*
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1542
题目大意:有n间房子,有两种操作:
1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空思路:记录区间中最长的空房间 ,
线段树操作:
update:区间替换
query:询问满足条件的最左端点 ,线段树每个节点记录
3个参数 :
lsum :左端开始的空余量 ;
rsum :右端开始的空余量 ;
msum : 最大空余量(可能在中间)
*/
#include<stdio.h>
#define N 50005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int lsum[N<<2],rsum[N<<2],msum[N<<2];
int add[N<<2];
int n,m;
int Max(int x,int y){
return x>y?x:y;
}
void pushup(int rt,int m){
lsum[rt] = lsum[rt<<1];
rsum[rt] = rsum[rt<<1|1];
if(lsum[rt] == m-(m>>1)) lsum[rt] += lsum[rt<<1|1];
if(rsum[rt] == (m>>1)) rsum[rt] += rsum[rt<<1];
msum[rt] = Max(rsum[rt<<1] + lsum[rt<<1|1],Max(msum[rt<<1],msum[rt<<1|1]));
}
void pushdown(int rt,int m){
if(add[rt] != -1){
add[rt<<1] = add[rt<<1|1] = add[rt];
lsum[rt<<1] = rsum[rt<<1] = msum[rt<<1] = add[rt] ? 0 : m-(m>>1);
lsum[rt<<1|1] = rsum[rt<<1|1] = msum[rt<<1|1] = add[rt] ? 0 : (m>>1);
add[rt] = -1;
}
}
void build(int rt,int l,int r){
lsum[rt] = rsum[rt] = msum[rt] = r-l+1;
add[rt] = -1;
if(l == r) return;
int mid = (l + r) >> 1;
build(lson);
build(rson);
}
int query(int rt,int l,int r,int w){
if(l == r) return l;
pushdown(rt,r-l+1);
int mid = (l + r) >> 1;
if(msum[rt<<1] >= w)
return query(lson,w);
else if(rsum[rt<<1] + lsum[rt<<1|1] >= w)
return mid-rsum[rt<<1]+1;
else
return query(rson,w);
}
void update(int rt,int l,int r,int L,int R,int w){
if(L <= l && R >= r){
lsum[rt] = rsum[rt] = msum[rt] = w ? 0 :r-l+1;
add[rt] = w;;
return;
}
pushdown(rt,r-l+1);
int mid = (l + r) >> 1;
if(L <= mid) update(lson,L,R,w);
if(R > mid ) update(rson,L,R,w);
pushup(rt,r-l+1);
}
int main(){
int i;
int op,a,b,c;
while(scanf("%d %d",&n,&m)!=EOF){
build(1,1,n);
for(i = 1; i <= m; ++i){
scanf("%d",&op);
if(op == 1){
scanf("%d",&c);
if(msum[1] < c)
puts("0");
else{
int res = query(1,1,n,c);
printf("%d\n",res);
update(1,1,n,res,res+c-1,1);
}
}
else{
scanf("%d %d",&a,&b);
update(1,1,n,a,a+b-1,0);
}
}
}
return 0;
}
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739733
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739064
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同...poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
POJ题解 个人写法 线段树每个人都不一样
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ3468,线段树处理,注意longlongint
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告