POJ 3667 线段树 + 延迟标记 + 区间处理
/*贴个神牛的代码，自己写的代码难看的别提有多恶心了 ...类型：线段树 + 延迟标记 + 区间合并... */#include<iostream>#include<cstring>#include<cctype>#include<cstdio>#include<algorithm>using namespace std;#define L(r) r<<1#define R(r) r<<1|1const int MAXM=50005;typedef struct{ int lsum,rsum,msum;//分别表示左边最大房间数，右边最大房间数，整体最大房间数 int cover;//是否住下}node;node tree[MAXM<<2];void pushDown(int root,int m)//向下更新{ if(tree[root].cover==-1) return;//是否已经更新 tree[L(root)].cover=tree[R(root)].cover=tree[root].cover; tree[L(root)].msum=tree[L(root)].lsum=tree[L(root)].rsum=tree[root].cover?0:m-(m>>1); tree[R(root)].msum=tree[R(root)].lsum=tree[R(root)].rsum=tree[root].cover?0:(m>>1); tree[root].cover=-1;}void pushUp(int root,int m)//向上更新{ tree[root].lsum=tree[L(root)].lsum; tree[root].rsum=tree[R(root)].rsum; if(tree[root].lsum==m-(m>>1) ) tree[root].lsum+=tree[R(root)].lsum; // 区间合并 if(tree[root].rsum==(m>>1) ) tree[root].rsum+=tree[L(root)].rsum; tree[root].msum=max(tree[R(root)].lsum+tree[L(root)].rsum,max(tree[L(root)].msum,tree[R(root)].msum) );}void Create(int l,int r,int root)//建树过程{ tree[root].cover=-1; tree[root].lsum=tree[root].rsum=tree[root].msum=r-l+1; if(l==r){return;} int mid=(l+r)>>1; Create(l,mid,L(root)); Create(mid+1,r,R(root));}void update(int ll,int rr,int c,int l,int r,int root)//更新{ if(ll<=l&&r<=rr)//如果找到这个范围就直接赋值返回，不向下继续更新 { tree[root].msum=tree[root].lsum=tree[root].rsum=c?0:r-l+1; tree[root].cover=c; return; } pushDown(root,r-l+1);//用到这个节点的子节点的时候就向下更新 int m=(l+r)>>1; if(ll<=m) update(ll,rr,c,l,m,L(root)); if(m<rr) update(ll,rr,c,m+1,r,R(root)); pushUp(root,r-l+1);//向下更新完后需要把节点信息反馈给父节点}int query(int w,int l,int r,int root)//查询满足连续房间数量的最左节点{ if(l==r) return l; pushDown(root,r-l+1 );//用到这个节点的子节点的时候就向下更新 int m=(l+r)>>1; //////////////////// 注意顺序， 区间的处理 if(tree[L(root)].msum>=w) return query(w,l,m,L(root));//如果左儿子满足就询问左儿子 else if(tree[L(root)].rsum+tree[R(root)].lsum>=w) return m-tree[L(root)].rsum+1;//如果左儿子和右儿子之间的数量满足，则范围左儿子右边连续房间第一个的编号 else return query(w,m+1,r,R(root));//如果两者都不满足则询问右儿子}int main(){ int n,m; while(~scanf("%d %d",&n,&m)) { Create(1,n,1); int a,num,x,d,p; for(int i=0;i<m;++i) { scanf("%d",&a); if(1==a) { scanf("%d",&num); if(tree[1].msum<num) puts("0");//如果整个区间的最大连续房间数量小于预定的数量就输出0 else { p=query(num,1,n,1);//找到最左节点p printf("%d\n",p); update(p,p+num-1,1,1,n,1);//把已经有人的房间标记一下 } } else { scanf("%d %d",&x,&d); update(x,x+d-1,0,1,n,1);//把此范围的房间标记成无人 } } } return 0;}