首页 > 代码库 > poj 3667Hotel(经典线段树)
poj 3667Hotel(经典线段树)
传送门:点击打开链接
题目大意:
有N个房间排在一列,有两种操作。
1:查询最靠左的长度为len的空房间,并且入住这些空房间。
2:以l开头,长度为r的房间退房。(如果本来就是空的 还是要退房)。
解题思路:
一类经典的线段树题目。区间合并类。
容易想到在查询上做做手脚,这题就差不多了。问题在于维护哪些东西。由于两个子区间要求合并,那么可以记录一个前最长可用连续,后最长可用连续,和连续可用的最大值。
那么pushup函数和pushdown函数就很简单了。
下面就是查询:如果左区间的连续值是大于等于要求的话,那么查左区间,如果右区间的连续值大于等于要求的话 ,查询右区间。
如果左区间的右连续+右区间的左连续大于等于要求的话。可以直接返回区间的最左下标。
注意:因为要求最偏左,所以注意顺序。
学了几天线段树了,感觉还是没怎么入门。慢慢来吧。
#include <cstdio> #include <algorithm> #define maxn 50010 using namespace std; struct Node { int l,r; int sum,pre,suf;//最长可用区间,左最长,右最长 int c;//0表示未被占用 ,1表示被占用 }tree[maxn<<2]; inline void pushup(int id) { if(tree[id<<1].sum == tree[id<<1].r-tree[id<<1].l+1) tree[id].pre = tree[id<<1].sum + tree[id<<1|1].pre; else tree[id].pre = tree[id<<1].pre; if(tree[id<<1|1].sum == tree[id<<1|1].r-tree[id<<1|1].l+1) tree[id].suf = tree[id<<1|1].sum + tree[id<<1].suf; else tree[id].suf = tree[id<<1|1].suf; tree[id].sum = max(max(tree[id<<1].sum,tree[id<<1|1].sum),tree[id<<1].suf+tree[id<<1|1].pre); } inline void pushdown(int id) { if(tree[id].c+1) { tree[id<<1].c = tree[id<<1|1].c = tree[id].c; int len = (tree[id].r- tree[id].l + 1); int len1 = len-(len>>1); int len2 = len>>1; if(tree[id].c)//标记是1,全部标记为不可用 { tree[id<<1].pre = 0; tree[id<<1].suf = 0; tree[id<<1].sum = 0; tree[id<<1|1].sum = 0; tree[id<<1|1].pre = 0; tree[id<<1|1].suf = 0; } else//标记是0,表示全部都可用 { tree[id<<1].pre = len1; tree[id<<1].suf = len1; tree[id<<1].sum = len1; tree[id<<1|1].sum = len2; tree[id<<1|1].pre = len2; tree[id<<1|1].suf = len2; } tree[id].c = -1; } } void build(int id,int l,int r) { tree[id].l = l; tree[id].r = r; tree[id].c = -1; if(l == r) { tree[id].sum = 1; tree[id].suf = 1; tree[id].pre = 1; return ; } int mid = (l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); pushup(id); } void op(int id,int l,int r,int c) { if(tree[id].l >= l &&tree[id].r <= r) { if(c) tree[id].pre = tree[id].suf = tree[id].sum = 0; else tree[id].pre = tree[id].suf = tree[id].sum = tree[id].r-tree[id].l+1; tree[id].c = c; return ; } pushdown(id); int mid = (tree[id].l + tree[id].r) >>1; if(l <= mid ) op(id<<1,l,r,c); if(mid < r) op(id<<1|1,l,r,c); pushup(id); } int query(int id,int len) { if(tree[id].l == tree[id].r) return tree[id].l; pushdown(id); int mid = (tree[id].l + tree[id].r)>>1; if(tree[id<<1].sum >= len) return query(id<<1,len); else if(tree[id<<1].suf + tree[id<<1|1].pre >= len) return mid - tree[id<<1].suf+1; else return query(id<<1|1,len); } int main() { int n,q; while(scanf("%d %d",&n,&q) != EOF) { build(1,1,n); while(q--) { int ch; scanf("%d",&ch); if(ch == 1) { int len; scanf("%d",&len); if(tree[1].sum < len) { printf("0\n"); continue; } int pos= query(1,len); printf("%d\n",pos); op(1,pos,pos+len-1,1); } else { int l,r; scanf("%d %d\n",&l,&r); op(1,l,l+r-1,0); } } } return 0; }
poj 3667Hotel(经典线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。