首页 > 代码库 > POJ 3667 Hotel.
POJ 3667 Hotel.
~~~~
线段树区间合并~
两种操作:
1、输出满足连续区间最左边的值。
2、更新一段连续区间。
题目链接:http://poj.org/problem?id=3667
~~~~
#include<cstdio> #include<cstring> #include<algorithm> #define INF 0x7fffffff #define lson rt<<1,s,m #define rson rt<<1|1,m+1,e #define N 55555 using namespace std; struct node { int v; int lm,rm,sm; }tre[N<<2]; void build(int rt,int s,int e) { tre[rt].v=-1; tre[rt].lm=tre[rt].rm=tre[rt].sm=e-s+1; if(s==e) return ; int m=(s+e)>>1; build(lson); build(rson); } void pushdown(int rt,int m) //成段更新操作。 { if(tre[rt].v!=-1) { tre[rt<<1].v=tre[rt<<1|1].v=tre[rt].v; tre[rt<<1].lm=tre[rt<<1].rm=tre[rt<<1].sm=tre[rt].v? 0:m-(m>>1); tre[rt<<1|1].lm=tre[rt<<1|1].rm=tre[rt<<1|1].sm=tre[rt].v? 0:m>>1; tre[rt].v=-1; } } void pushup(int rt,int m) //区间合并操作。 { tre[rt].lm=tre[rt<<1].lm; tre[rt].rm=tre[rt<<1|1].rm; if(tre[rt].lm==m-(m>>1)) tre[rt].lm+=tre[rt<<1|1].lm; if(tre[rt].rm==(m>>1)) tre[rt].rm+=tre[rt<<1].rm; tre[rt].sm=max(tre[rt<<1].sm,max(tre[rt<<1|1].sm,tre[rt<<1].rm+tre[rt<<1|1].lm)); } int query(int n,int rt,int s,int e) { if(s==e) return s; pushdown(rt,e-s+1); int m=(s+e)>>1; //因为要输出最左边的位置。 if(tre[rt<<1].sm>=n) return query(n,lson); else if(tre[rt<<1].rm+tre[rt<<1|1].lm>=n) return m-tre[rt<<1].rm+1; //两个子区间的中间区域。 else return query(n,rson); } void update(int l,int r,int v,int rt,int s,int e) { if(l==s && r==e) { tre[rt].v=v; tre[rt].lm=tre[rt].rm=tre[rt].sm=v? 0:e-s+1; return ; } pushdown(rt,e-s+1); int m=(s+e)>>1; if(r<=m) update(l,r,v,lson); else if(l>m) update(l,r,v,rson); else { update(l,m,v,lson); update(m+1,r,v,rson); } pushup(rt,e-s+1); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { build(1,1,n); for(int i=0;i<m;i++) { int op; scanf("%d",&op); if(op==1) { int num; scanf("%d",&num); if(tre[1].sm>=num) { int k=query(num,1,1,n); printf("%d\n",k); update(k,k+num-1,1,1,1,n); } else puts("0"); } else { int k,num; scanf("%d %d",&k,&num); update(k,k+num-1,0,1,1,n); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。