poj 3667 Hotel(线段树区间更新)

poj 3667 Hotel(线段树区间更新)

题目：​​ a”表示要求查询是否存在连续的a个空的房间，有的话输出最左边的一个，没有的话输出0。“2 a b"表示把从a开始的b个房间清空。

Sample Input

10 6 1 3 1 3 1 3 1 3 2 5 5 1 6

Sample Output

1 4 7 0 5

区间更新，区间查找。应用线段树：

#include #include #include using namespace std;const int N = 50005; //query:询问满足条件的最左端点struct Node{ int l,r; int lsum,rsum,msum; //三个值，帮助确定左边，中间，右边 int tag; //tag --> 标记，1是占用的，0是未占用，-1初始化 int mid(){ return (l+r)/2; }}tree[N<<2];void pushdown(int root)//更新子树tag,lsum,rsum,msum的信息{ if(tree[root].tag != -1) { int l_num = tree[root*2].r - tree[root*2].l + 1; //左子树的长度 int r_num = tree[root*2+1].r - tree[root*2+1].l + 1; //右子树的长度 tree[root*2].tag = tree[root*2+1].tag = tree[root].tag; //要处理 tree[root].tag = -1; //处理过了的 tree[root*2].rsum = tree[root*2].lsum = tree[root*2].msum = tree[root*2].tag ?0:l_num; tree[root*2+1].rsum = tree[root*2+1].lsum = tree[root*2+1].msum = tree[root*2+1].tag ?0:r_num; }}void pushup(int root)//更新父节点lsum,rsum,msum的信息,msum是最大的sum{ int l_num = tree[root*2].r - tree[root*2].l + 1; int r_num = tree[root*2+1].r - tree[root*2+1].l + 1; tree[root].lsum = tree[root*2].lsum; if(tree[root*2].lsum == l_num) tree[root].lsum += tree[root*2+1].lsum; //可向右拓展，越过中间 tree[root].rsum = tree[root*2+1].rsum; if(tree[root].rsum == r_num) tree[root].rsum += tree[root*2].rsum; //可向左拓展，越过中间 tree[root].msum = max(max(tree[root*2].msum,tree[root*2+1].msum),tree[root*2].rsum+tree[root*2+1].lsum);}void build(int l,int r,int root){ tree[root].l = l,tree[root].r = r,tree[root].tag = -1; tree[root].lsum = tree[root].rsum = tree[root].msum = r-l+1; if(l == r) return; int m = (l+r)>>1; build(l,m,root*2); build(m+1,r,root*2+1); pushup(root);}void update(int l,int r,int tg,int root){ if(tree[root].l == l && tree[root].r == r) { tree[root].msum = tree[root].lsum = tree[root].rsum = tg?0:(r-l+1); tree[root].tag = tg; return; } pushdown(root); //更新子树信息 int m = tree[root].mid(); if(r<=m) update(l,r,tg,root*2); else if(l>m) update(l,r,tg,root*2+1); else { update(l,m,tg,root*2); update(m+1,r,tg,root*2+1); } pushup(root); //回溯信息。}int query(int w,int root){ if (tree[root].l == tree[root].r) return tree[root].l; pushdown(root); //依据tag更新信息再统计 int m = tree[root].mid(); if (tree[root*2].msum >= w) return query(w,root*2); //这段代码很重要 else if (tree[root*2].rsum + tree[root*2+1].lsum >= w)//中间的情况 return m - tree[root*2].rsum + 1; //主要依靠中间区域和叶子节点返回信息 return query(w,root*2+1); //右边}int main(){ //freopen("cin.txt","r",stdin); int n,m; while(cin>>n>>m) { build(1,n,1); while(m--) { int p; scanf("%d",&p); if(p == 1) { int a; scanf("%d",&a); if(tree[1].msum < a) puts("0"); else { int ans = query(a,1); printf("%d\n",ans); update(ans,ans+a-1,1,1); } } else { int a,b; scanf("%d %d",&a,&b); update(a,a+b-1,0,1); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。