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

本文主要是介绍poj 3667 Hotel(线段树区间更新)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://poj.org/problem?id=3667

大意：有N个房间，给出M条语句，“1  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 <iostream>
#include <cstdio>
#include <algorithm>
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;
}

这篇关于poj 3667 Hotel(线段树区间更新)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---