Hotel POJ - 3667(線段樹 + 區間合并

題意：給定長度為n的區間，有2個操作：

操作1：在區間中靠左放k個元素，輸出新放入元素中最左邊的位置，如果放不下輸出 0；

操作2 ：清空 l 到 l+w-1這一段區間的元素

這裡有一個狀态轉移方程（即線段樹的上推方式）：

線段樹區間pos中儲存 lcon--從區間左端L最大連續的區間長度， rcon--從線段樹右端R最大連續的區間長度，mcon 區間内最大的區間長度

則： t[pos].mcon = max{ t[Lpos].rcon+t[Rpos].lcon ，t[Lpos].mcon ,t[Rpos].mcon );

t[pos].lcon = t[Lpos].lcon+（t[Rpos],lcon）; t[pos].rcon = t[Rpos].rcon+（t[Lpos].rcon） (如果左或右區間整段連續，就加上括号裡面的部分

lazy标記的下移（對整段空或整段滿的區間進行标記）：

void pushdown( int L ,int R, int pos){
    if( t[pos].tag!=0 && t[pos].tag!=1 ) return ;
    int Mid;
     t[posl].tag = t[posr].tag =t[pos].tag;
     t[posl].mcon = t[posl].lcon = t[posl].rcon = t[pos].tag ? mid - L+1 : 0 ;
     t[posr].mcon = t[posr].lcon = t[posr].rcon = t[pos].tag ? R-mid : 0 ;
     t[pos].tag = -1;
     return ;
}

查詢：

判斷能否放下：比較k與總區間最大連續區間長度t[ 1 ].mcon 的大小

查詢新放入元素最左坐标：如果左區間最大連續空區間大于目标長度就一直查詢左區間，直到查詢不了就判斷左區間右連續加上右區間左連續可不可以，可以就輸出結果，不行的話在查詢右區間

int query(  int L ,int R ,int pos ,int w ){
     if( L==R ) return L;
    // cout<< L <<' '<<R << ' '<<w<<endl;
     pushdown( L ,R ,pos);
     int Mid;
     if( t[posl].mcon >= w ) return query( lson , w);                                           //優先查左邊
     else if( t[posl].rcon + t[posr].lcon >= w) return mid - t[posl].rcon +1 ; //查到左邊放不下了，輸出區間放在中間的結果
     else return query( rson ,w);                                                                            //中間放不了，最末查詢右邊
}

更新比較平常，就不說了

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define posl pos<<1
#define posr pos<<1|1
#define lson L ,mid ,posl
#define rson mid+1 ,R ,posr
#define Mid mid=(L+R)>>1

struct tree{
     int lcon ,rcon ,mcon;
     int  tag;
} t[50005<<2];
void pushup( int L ,int R ,int pos){
     t[pos].lcon = t[posl].lcon;
     t[pos].rcon = t[posr].rcon;
     int Mid;
     if( t[pos].lcon == mid - L +1 ) t[pos].lcon += t[posr].lcon;
     if( t[pos].rcon == R - mid ) t[pos].rcon += t[posl].rcon;
     t[pos].mcon = max( t[posl].rcon+t[posr].lcon ,max( t[posl].mcon  ,t[posr].mcon));
}

void pushdown( int L ,int R, int pos){
    if( t[pos].tag!=0 && t[pos].tag!=1 ) return ;
    int Mid;
     t[posl].tag = t[posr].tag =t[pos].tag;
     t[posl].mcon = t[posl].lcon = t[posl].rcon = t[pos].tag ? mid - L+1 : 0 ;
     t[posr].mcon = t[posr].lcon = t[posr].rcon = t[pos].tag ? R-mid : 0 ;
     t[pos].tag = -1;
     return ;
}

void build( int L ,int R ,int pos){
     t[pos].tag = -1;
     t[pos].lcon = t[pos].rcon = t[pos].mcon = R - L +1;
     if( L == R) return ;
     int Mid;
     build( lson);
     build( rson);
}

void updata( int L ,int R ,int pos ,int l,int r,int v ){
     if( L>= l && R <= r ){

        t[pos].mcon = t[pos].rcon = t[pos].lcon = v ? R - L +1 : 0 ;
        t[pos].tag = v;
        return ;
     }
     if( L == R)return;
     pushdown( L ,R ,pos);
     int Mid;
     if( l <= mid ) updata( lson ,l ,r ,v);
     if( mid < r) updata( rson ,l ,r ,v);
     pushup( L ,R ,pos);
}

int query(  int L ,int R ,int pos ,int w ){
     if( L==R ) return L;
    // cout<< L <<' '<<R << ' '<<w<<endl;
     pushdown( L ,R ,pos);
     int Mid;
     if( t[posl].mcon >= w ) return query( lson , w);                                           //優先查左邊
     else if( t[posl].rcon + t[posr].lcon >= w) return mid - t[posl].rcon +1 ; //查到左邊放不下了，輸出區間放在中間的結果
     else return query( rson ,w);                                                                            //中間放不了，最末查詢右邊
}
int main( ){
     int n,m;
     scanf( "%d%d" ,&n ,&m);
     build( 1 ,n ,1);
     while( m-- ){
         int op ,k ,l ,r;
         scanf("%d" ,&op);
         if( op ==1){
             scanf("%d" ,&k);
             if( t[1].mcon >=k){
                 l=query( 1 ,n ,1 ,k);
                 updata( 1 , n ,1 ,l ,l+k-1, 0);
                 printf("%d\n" ,l);
             }
             else printf("0\n");
         }
         else{
             scanf("%d%d",&l ,&r);
             updata( 1 ,n ,1 ,l ,l+r-1,1);
         }
     }
     return 0;
}

轉載于:https://www.cnblogs.com/-ifrush/p/10632421.html