hdu6315（ 2018 Multi-University Training Contest 2）

http://acm.hdu.edu.cn/showproblem.php?pid=6315
/*hdu 1007

首先我们在建立线段树之前应该思考的是线段树的节点维护一个什么值，

在比赛过程中，我想到了维护a[i]的值但是时间复杂度太高，又想到维护a[i]/b[i]但是取下整，

这样的话无法更新∑的值。

在题解中，维护了b[i]的值，因为a[i]最初是0，所以在update过程中当a[i]>=b[i]时,a[i]/b[i]才>=1；

才会对sum有贡献，所以不妨维护b[i]的值，对每次区间更新，将区间中的b[i]减1，当b[i]减到0时，更新sum的值+1,然后b[i]更新回初始的b[i]的值

整个更新过程中需要维护lazy标志、numzero当前子树中0的个数（即sum+1的次数）、minx当前子树中最小的b[i]值、valb当前节点初始的b[i]值

*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

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

const int MAXN=201000;

struct

{

    int minx,valb,numzero;

    int lazy;

}sum[MAXN<<2];

int b[MAXN];

void push_up(int rt)

{

    sum[rt].numzero=sum[rt<<1].numzero+sum[rt<<1|1].numzero;

    sum[rt].minx=min(sum[rt<<1].minx,sum[rt<<1|1].minx);

}

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

{

    sum[rt<<1].lazy+=sum[rt].lazy;

    sum[rt<<1|1].lazy+=sum[rt].lazy;

    sum[rt<<1].minx-=sum[rt].lazy;

    sum[rt<<1|1].minx-=sum[rt].lazy;

    sum[rt].lazy=0;

}

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

{

    sum[rt].lazy=0;

    sum[rt].numzero=0;

    if(l==r)

    {

        sum[rt].lazy=0;

        sum[rt].minx=b[l];

        sum[rt].numzero=0;

        sum[rt].valb=b[l];

        return;

    }

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

    build(lson);

    build(rson);

    push_up(rt);

}

/*update操作

*/

void update(int L,int R,int l,int r,int rt=1)

{

    if(L<=l&&r<=R&&sum[rt].minx>1)

    {

        sum[rt].lazy++;

        sum[rt].minx--;

        return;

    }

    if(l==r&&sum[rt].minx==1)

    {

        sum[rt].numzero++;

        sum[rt].lazy=0;

        sum[rt].minx=sum[rt].valb;

        return;

    }

    if(sum[rt].lazy>0)

        push_down(rt,l,r);

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

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

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

    push_up(rt);

}

/*query操作

求和操作，就是求子树中numzero和

*/

int query(int L,int R,int l,int r,int rt=1)

{

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

    {

        return sum[rt].numzero;

    }

    if(sum[rt].lazy>0)push_down(rt,l,r);

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

    int ret=0;

    if(L<=m)ret+=query(L,R,lson);

    if(R>m)ret+=query(L,R,rson);

    return ret;

}

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int n,m;

    while(cin>>n>>m)

    {

        memset(b,0,sizeof(b));

        char ch[10];

        int L,R;

        for(int i=1;i<=n;i++)

            scanf("%d",b+i);

        build(1,n,1);

        while(m--)

        {

            scanf("%s",ch);

            scanf("%d%d",&L,&R);

            if(ch[0]=='a')

            {

                update(L,R,1,n,1);

            }

            else if(ch[0]=='q')

            {

                printf("%d\n",query(L,R,1,n,1));

            }

        }

    }

    return 0;

}
巴特西

hdu6315（ 2018 Multi-University Training Contest 2）

最新文章

热门文章
