hdu4553（线段树）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4553

线段树功能：update:区间替换 query:询问满足条件的最左断点

分析：poj3667的加强版，这里需要在每个区间内设置女神区间和屌丝区间，每次询问女神的时候，先看屌丝区间有无空位，有就插到屌丝区间内，同时更新女神区间，否则插到女神区间内，但同时也要更新屌丝区间，因为只有女神可以占用屌丝的时间，屌丝不能占用女神的时间，每次更新屌丝区间的时候直接更新即可，清空的话就是对屌丝和女神的区间都清空。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define M 1000000000

#define maxn 55555

#define lson l,m,rt<<1

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

using namespace std;

int lsum[maxn<<],rsum[maxn<<],sum[maxn<<];

int col[maxn<<];

void PushDown(int rt,int m)

{

    if(col[rt]!=-)

    {

        col[rt<<]=col[rt<<|]=col[rt];

        sum[rt<<]=lsum[rt<<]=rsum[rt<<]=col[rt]?:m-(m>>);

        sum[rt<<|]=lsum[rt<<|]=rsum[rt<<|]=col[rt]?:m>>;

        col[rt]=-;

    }

}

void PushUp(int rt,int m)

{

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

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

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

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

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

}

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

{

    col[rt]=-;

    sum[rt]=lsum[rt]=rsum[rt]=r-l+;

    if(l==r)return;

    int m=(r+l)>>;

    build(lson);

    build(rson);

}

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

{

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

    {

        sum[rt]=lsum[rt]=rsum[rt]=c?:r-l+;

        col[rt]=c;

        return;

    }

    PushDown(rt,r-l+);

    int m=(r+l)>>;

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

    if(R>m)update(L,R,c,rson);

    PushUp(rt,r-l+);

}

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

{

    if(l==r)return l;

    PushDown(rt,r-l+);

    int m=(r+l)>>;

    if(sum[rt<<]>=w)return query(w,lson);

    else if(rsum[rt<<]+lsum[rt<<|]>=w)return m-rsum[rt<<]+;

    else return query(w,rson);

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)>)

    {

        build(,n,);

        while(m--)

        {

            int a,b,op;

            scanf("%d",&op);

            if(op==)

            {

                scanf("%d",&a);

                if(sum[]<a)puts("");

                else

                {

                    int ans=query(a,,n,);

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

                    update(ans,ans+a-,,,n,);

                }

            }

            else

            {

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

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

            }

        }

    }

}

巴特西

hdu4553（线段树）

最新文章

热门文章