poj_3667线段树区间合并

对照着notonlysuccess大牛的代码写的
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int maxn=55555;

int msum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2],cover[maxn<<2];

void build(int l,int r,int rt)

{

    cover[rt]=-1;

    msum[rt]=lsum[rt]=rsum[rt]=r-l+1;

    if(l==r) return ;

    int m=(r+l)>>1;

    build(lson);

    build(rson);

}

void pushUp(int rt,int m)

{

    lsum[rt]=lsum[rt<<1];

    rsum[rt]=rsum[rt<<1|1];

    if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];

	if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];

	msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));

}

void pushdown(int rt,int m)

{

    if(cover[rt]!=-1)

    {

        cover[rt<<1] = cover[rt<<1|1] = cover[rt];

        msum[rt<<1]=rsum[rt<<1]=lsum[rt<<1]=cover[rt]?0:m-(m>>1);

        msum[rt<<1|1]=rsum[rt<<1|1]=lsum[rt<<1|1]=cover[rt]?0:m>>1;

        cover[rt]=-1;

    }

}

void update(int L,int R,int b,int l,int r,int rt)

{

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

    {

        msum[rt]=lsum[rt]=rsum[rt]=b?0:r-l+1;

        cover[rt]=b;

        return;

    }

    pushdown(rt,r-l+1);

    int m=(r+l)>>1;

    if(L<=m) update(L,R,b,lson);

    if(m<R) update(L,R,b,rson);

    pushUp(rt,r-l+1);

}

int query(int a,int l,int r,int rt)

{

    if(l==r) return l;

    pushdown(rt,r-l+1);

    int m=(r+l)>>1;

    if(msum[rt<<1]>=a) return query(a,lson);

    else if(lsum[rt<<1|1]+rsum[rt<<1]>=a)

        return m-rsum[rt<<1]+1;

    return query(a,rson);

}

int main()

{

    int n,m;

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

    build(1,n,1);

    for(int i=0;i<m;i++)

    {

        int op,a,b;

        scanf("%d",&op);

        if(op==1)

        {

            scanf("%d",&a);

            if(msum[1]<a) puts("0");

            //printf("0\n");

            else{

            int p=query(a,1,n,1);

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

            //cout<<"##"<<endl;

            update(p,p+a-1,1,1,n,1);

            }

        }

        else

        {

            scanf("%d%d",&a,&b);

            //cout<<"############"<<endl;

            update(a,a+b-1,0,1,n,1);

           // cout<<msum[1]<<"$$"<<endl;

        }

    }

    return 0;

}
巴特西

poj_3667线段树区间合并

最新文章

热门文章
