poj 3468 A Simple Problem with Integers（线段树插线问线）

#include<iostream>

#include<stdio.h>

#include<string.h>

#define NN 2500000

using namespace std;

typedef  long long LL;

struct node

{

    LL l,r,sum,flag;

} N[NN];

void build(LL l,LL r,LL i)

{

    LL mid=(l+r)>>1;

    N[i].flag=0;

    N[i].l=l;

    N[i].r=r;

    N[i].sum=0;

    if(l==r)

    {

        scanf("%lld",&N[i].sum);

        return ;

    }

    build(l,mid,i*2);

    build(mid+1,r,i*2+1);

    N[i].sum=N[i*2].sum+N[i*2+1].sum;

}

void renew(LL i,LL l,LL r,LL k)

{

    LL mid=(N[i].l+N[i].r)>>1;

    if(N[i].l==l&&N[i].r==r)

    {

        N[i].flag+=k;

        return ;

    }

    N[i].sum+=(r-l+1)*k;

    if(mid<l) renew(i*2+1,l,r,k);

    else if(mid>=r)renew(i*2,l,r,k);

    else

    {

        renew(i*2,l,mid,k);

        renew(i*2+1,mid+1,r,k);

    }

}

LL query(LL i,LL l,LL r)

{

    LL mid=(N[i].l+N[i].r)>>1;

    if(l==N[i].l&&r==N[i].r)

    {

        return N[i].sum+(r-l+1)*N[i].flag;

    }

    if(N[i].flag)

    {

        N[i*2].flag+=N[i].flag;

        N[i*2+1].flag+=N[i].flag;

        N[i].sum+=(N[i].r-N[i].l+1)*N[i].flag;

        N[i].flag=0;

    }

    if(l>mid) return query(i*2+1,l,r);

    else if(r<=mid)  return query(i*2,l,r);

    else

    {

        return query(i*2+1,mid+1,r)+query(i*2,l,mid);

    }

}

int main()

{

    LL n,m,suzi,a,b,i;

    char s[5];

    while(scanf("%lld %lld",&n,&m)!=EOF)

    {

        build(1,n,1);

        //   prLLf("sdd=%lld\n",N[8].sum);

        //  return 0;

        for(i=1; i<=m; i++)

        {

            scanf("%s",s);

            // return 0;

            if(s[0]=='C')

            {

                LL a,b,c;

                scanf("%lld %lld %lld",&a,&b,&c);

                renew(1,a,b,c);

            }

            else

            {

                LL a,b;

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

                printf("%lld\n",query(1,a,b));

            }

        }

    }

    return 0;

}

巴特西

poj 3468 A Simple Problem with Integers（线段树插线问线）

最新文章

热门文章

巴特西

poj 3468 A Simple Problem with Integers（线段树 插线问线）

最新文章

热门文章

poj 3468 A Simple Problem with Integers（线段树插线问线）