[题解]（线段树最大连续子段和）POJ_3667_Hotel

题意：1.求一个最靠左的长x的区间全部为0，并修改为1，输出这个区间的左端点

2.修改一个区间为0

实际上是维护最大连续子段和，原来也写过

大概需要维护一个左/右最大子段和，当前这段最大子段长，再维护一个lazytag

#include<iostream>

#include<cstdio>

#include<cstring>

#define mid (l+r>>1)

#define ls x<<1

#define rs x<<1|1

using namespace std;

const int maxn=;

struct node{

    int l,r,mx,tg;//0全空,1全满,-1没有

}t[maxn<<];

//inline void upd(int x,int l,int r){

//    t[x].l=t[ls].l;

//    t[x].r=t[rs].r;

////    if(t[ls].l==mid-l+1)t[x].l+=t[rs].l;

////    if(t[rs].r==r-mid)t[x].r+=t[ls].r;

//    if(t[ls].l==(r-l+1-(r-l+1)/2))t[x].l+=t[rs].l;

//    if(t[rs].r==(r-l+1)/2)t[x].r+=t[ls].r;

//    t[x].mx=max(max(t[ls].mx,t[rs].mx),t[ls].r+t[rs].l);

//}

//inline void pushdown(int x,int l,int r){

//    if(t[x].tg!=-1){

//        t[ls].tg=t[rs].tg=t[x].tg;

//        t[ls].l=t[ls].r=t[ls].mx=(r-l+1-(r-l+1)/2)*t[x].tg;

//        t[rs].l=t[rs].r=t[rs].mx=(r-l+1)/2*t[x].tg;

////        if(t[x].tg==0){

////            t[ls].l=t[ls].r=t[ls].mx=mid-l+1;

////            t[rs].l=t[rs].r=t[rs].mx=r-mid;

////        }

////        else{

////            t[ls].l=t[ls].r=t[ls].mx=0;

////            t[rs].l=t[rs].r=t[rs].mx=0;

////        }

//        t[x].tg=-1;

//    }

//}

inline void pushdown(int x,int len){

    if(t[x].tg!=-){

        t[ls].tg=t[rs].tg=t[x].tg;

        t[ls].mx=t[ls].l=t[ls].r=t[x].tg*(len-(len>>));

        t[rs].mx=t[rs].l=t[rs].r=t[x].tg*(len>>);

        t[x].tg=-;

    }

}

inline void upd(int x,int len){

    t[x].l=t[ls].l;

    t[x].r=t[rs].r;

    if(t[x].l==len-(len>>))t[x].l+=t[rs].l;

    if(t[x].r==(len>>))t[x].r+=t[ls].r;

    t[x].mx=max(max(t[ls].mx,t[rs].mx),t[ls].r+t[rs].l);

}

void build(int x,int l,int r){

    t[x].l=t[x].r=t[x].mx=r-l+;t[x].tg=-;

    if(l==r)return;

    build(ls,l,mid);build(rs,mid+,r);

}

void change(int x,int l,int r,int L,int R,int k){

    if(L<=l && r<=R){

        t[x].l=t[x].r=t[x].mx= k==?:r-l+;

        t[x].tg=k;

        return;

    }

//    pushdown(x,l,r);

    pushdown(x,r-l+);

    if(L<=mid)change(ls,l,mid,L,R,k);

    if(R>mid)change(rs,mid+,r,L,R,k);

//    upd(x,l,r);

    upd(x,r-l+);

}

int query(int x,int l,int r,int k){

    if(l==r)return ;

//    pushdown(x,l,r);

    pushdown(x,r-l+);

    if(t[ls].mx>=k)return query(ls,l,mid,k);

    else if(t[ls].r+t[rs].l>=k)return mid-t[ls].r+;

    else return query(rs,mid+,r,k);

}

int n,m;

int main(){

    scanf("%d%d",&n,&m);

    build(,,n);

    for(int i=,op,x,y;i<=m;i++){

        scanf("%d",&op);

        if(op==){

            scanf("%d",&x);

            if(t[].mx<x)printf("0\n");

            else{

                int pos=query(,,n,x);

                printf("%d\n",pos);

                change(,,n,pos,pos+x-,);

            }

        }

        else{

            scanf("%d%d",&x,&y);

            change(,,n,x,x+y-,);

        }

    }

}