POJ 3667（线段树区间合并）

题意：两个操作： 1 选出靠左的长度为a的区间。

2 把从 a到a+b的区间清空。

线段树区间合并+lazy

// by caonima
// hehe
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAX= 1e5+10;
int Lsum[MAX<<2],Rsum[MAX<<2],Msum[MAX<<2];
int col[MAX<<2];

void push_up(int o,int m) {
    Lsum[o]=Lsum[o<<1];
    Rsum[o]=Rsum[o<<1|1];
    if(Lsum[o]==(m-(m>>1))) Lsum[o]+=Lsum[o<<1|1];
    if(Rsum[o]==(m>>1)) Rsum[o]+=Rsum[o<<1];
    Msum[o]=max(max(Msum[o<<1],Msum[o<<1|1]),Rsum[o<<1]+Lsum[o<<1|1]);
    return ;
}
void push_down(int o,int m) {
    if(col[o]!=-1) {
        col[o<<1]=col[o<<1|1]=col[o];
        Lsum[o<<1]=Rsum[o<<1]=M
        sum[o<<1]= col[o] ? 0 : (m-(m>>1));
        Lsum[o<<1|1]=Rsum[o<<1|1]=Msum[o<<1|1]= col[o] ? 0 : ((m>>1));
        col[o]=-1;
    }
}
void build(int L,int R,int o) {
    col[o]=-1;
    if(L==R) {
        Lsum[o]=Rsum[o]=Msum[o]=1;
        return ;
    }
    int mid=(L+R)>>1;
    build(L,mid,o<<1);
    build(mid+1,R,o<<1|1);
    push_up(o,R-L+1);
}

int Query(int L,int R,int o,int len) {
    if(L==R) {
        return L;
    }
    push_down(o,R-L+1);
    int mid=(L+R)>>1;
    if(Msum[o<<1]>=len)  return Query(L,mid,o<<1,len);
    else if(Rsum[o<<1]+Lsum[o<<1|1]>=len) return mid-Rsum[o<<1]+1;
    else return Query(mid+1,R,o<<1|1,len);
    push_up(o,R-L+1);

}

void Update(int L,int R,int o,int ls,int rs,int val) {
    if(ls<=L&&rs>=R) {
        Msum[o]=Lsum[o]=Rsum[o]= val ? 0 : (R-L+1);
        col[o]=val;
        return ;
    }
    push_down(o,R-L+1);
    int mid=(L+R)>>1;
    if(ls<=mid) Update(L,mid,o<<1,ls,rs,val);
    if(rs>mid) Update(mid+1,R,o<<1|1,ls,rs,val);
    push_up(o,R-L+1);
}

int main() {
    int n,m,op,v,ls,rs;
    while(scanf("%d %d",&n,&m)==2) {
        build(1,n,1);
        for(int i=0;i<m;i++) {
            scanf("%d",&op);
            if(op==1) {
                scanf("%d",&v);
                if(Msum[1]<v) printf("0 ");
                else {
                    int res=Query(1,n,1,v);
                    printf("%d ",res);
                    Update(1,n,1,res,res+v-1,1);
                }
            }
            else {
                scanf("%d %d",&ls,&rs);
                Update(1,n,1,ls,ls+rs-1,0);
            }
        }
    }
    return 0;

}