poj 3468 A Simple Problem with Integers 线段树加延迟标记

时间：2021-08-05 19:46:54
A Simple Problem with Integers
 

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

Sample Output

4

55

9

15

Hint

The sums may exceed the range of 32-bit integers.

Source

思路：简单的区间更新跟区间求和，注意会爆int 
#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

#define true ture

#define false flase

using namespace std;

#define ll long long

int scan()

{

    int res =  , ch ;

    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )

    {

        if( ch == EOF )  return  <<  ;

    }

    res = ch - '' ;

    while( ( ch = getchar() ) >= '' && ch <= '' )

        res = res *  + ( ch - '' ) ;

    return res ;

}

struct is

{

    ll l,r;

    ll num;

    ll lazy;

}tree[*];

void build_tree(ll l,ll r,ll pos)

{

    tree[pos].l=l;

    tree[pos].r=r;

    tree[pos].lazy=;

    if(l==r)

    {

        //tree[pos].num=1;

        scanf("%lld",&tree[pos].num);

        return;

    }

    ll mid=(l+r)/;

    build_tree(l,mid,pos*);

    build_tree(mid+,r,pos*+);

    tree[pos].num=tree[pos*].num+tree[pos*+].num;

}

void update(ll l,ll r,ll change,ll pos)

{

    if(tree[pos].l==l&&tree[pos].r==r)

    {

        tree[pos].lazy+=change;

        tree[pos].num+=(tree[pos].r-tree[pos].l+)*change;

        return;

    }

    if(tree[pos].lazy)

    {

        tree[pos*].num+=(tree[pos*].r+-tree[pos*].l)*tree[pos].lazy;

        tree[pos*+].num+=(tree[pos*+].r+-tree[pos*+].l)*tree[pos].lazy;

        tree[pos*].lazy+=tree[pos].lazy;

        tree[pos*+].lazy+=tree[pos].lazy;

        tree[pos].lazy=;

    }

    ll mid=(tree[pos].l+tree[pos].r)/;

    if(r<=mid)

    update(l,r,change,pos*);

    else if(l>mid)

    update(l,r,change,pos*+);

    else

    {

        update(l,mid,change,pos*);

        update(mid+,r,change,pos*+);

    }

    tree[pos].num=tree[pos*].num+tree[pos*+].num;

}

ll query(ll l,ll r,ll pos)

{

    //cout<<l<<" "<<r<<" "<<pos<<endl;

    if(tree[pos].l==l&&tree[pos].r==r)

    return tree[pos].num;

    if(tree[pos].lazy)

    {

        tree[pos*].num+=(tree[pos*].r+-tree[pos*].l)*tree[pos].lazy;

        tree[pos*+].num+=(tree[pos*+].r+-tree[pos*+].l)*tree[pos].lazy;

        tree[pos*].lazy+=tree[pos].lazy;

        tree[pos*+].lazy+=tree[pos].lazy;

        tree[pos].lazy=;

    }

    ll mid=(tree[pos].l+tree[pos].r)/;

    if(l>mid)

    return query(l,r,pos*+);

    else if(r<=mid)

    return query(l,r,pos*);

    else

    return query(l,mid,pos*)+query(mid+,r,pos*+);

}

int main()

{

    ll x,q,i,t;

    while(~scanf("%lld",&x))

    {

        scanf("%lld",&q);

        build_tree(,x,);

        while(q--)

        {

            char a[];

            ll l,r;

            ll change;

            scanf("%s%lld%lld",a,&l,&r);

            if(a[]=='C')

            {

                scanf("%lld",&change);

                update(l,r,change,);

            }

            else

            printf("%lld\n",query(l,r,));

        }

    }

    return ;

}

相关文章