POJ 3667-hotel(线段树区间合并)

题意：有n个房间排成一排，有m个操作，对于操作1，询问是否有长度为v的连续的空房间，如果有，输出最小的左边的房间的编号，然后旅客将住进这些房间。对于操作2，将x开始，长度为D的房间清空。

思路：线段树。用3个数组sum,lsum,rsum分别记录当前区间的最长连续空房间的长度、从区间最左边开始最长连续空房间的长度、从区间右边开始最长连续空房间的长度。每次更新时，sum要么等于左右儿子的sum的最大值，要么等于左儿子的rsum的值加上右儿子的lsum的值，lsum和rsum更新方法类似。查询时，如果v>sum[1]，则说明没有大于等于v的连续空房子，直接输出0。否则，从左到右查询是否有大于等于v的值。

/****************************
* author:crazy_石头
* date：2014/04/29
* time: 625 ms
* algorithm:线段树区间并 
* Pro：POJ 3367
***************************/
#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             using namespace std; #define INF INT_MAX #define eps 1e-8 #define A system("pause") #define rep(i,h,n) for(int i=(h);i<=(n);i++) #define ms(a,b) memset((a),(b),sizeof(a)) #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 #define LL long long const int maxn=50000+5; const int maxm=30; int sum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2],set[maxn<<2]; inline void pushup(int l,int r,int rt) { int m=(l+r)>>1; sum[rt]=std::max(sum[rt<<1],sum[rt<<1|1]); sum[rt]=std::max(sum[rt],rsum[rt<<1]+lsum[rt<<1|1]); lsum[rt]=lsum[rt<<1]; if(lsum[rt<<1]==m-l+1) lsum[rt]+=lsum[rt<<1|1]; rsum[rt]=rsum[rt<<1|1]; if(rsum[rt<<1|1]==r-m) rsum[rt]+=rsum[rt<<1]; } inline void pushdown(int l,int r,int rt) { if(set[rt]>=0) { int m=(l+r)>>1; set[rt<<1]=set[rt<<1|1]=set[rt]; lsum[rt<<1]=rsum[rt<<1]=sum[rt<<1]=set[rt]?0:m-l+1; lsum[rt<<1|1]=rsum[rt<<1|1]=sum[rt<<1|1]=set[rt]?0:r-m; set[rt]=-1; } } inline void build(int l,int r,int rt) { sum[rt]=lsum[rt]=rsum[rt]=r-l+1; set[rt]=-1; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } inline void update(int v,int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { set[rt]=v; lsum[rt]=rsum[rt]=sum[rt]=v?0:r-l+1; return ; } int m=(l+r)>>1; pushdown(l,r,rt); if(L<=m) update(v,L,R,lson); if(R>m) update(v,L,R,rson); pushup(l,r,rt); } inline int query(int v,int l,int r,int rt) { if(l==r) return l; pushdown(l,r,rt); int m=(l+r)>>1; if(sum[rt<<1]>=v) return query(v,lson); if(lsum[rt<<1|1]+rsum[rt<<1]>=v) return m-rsum[rt<<1]+1; return query(v,rson); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { build(1,n,1); while(m--) { int op; scanf("%d",&op); if(op==1) { int v; scanf("%d",&v); if(sum[1]