C - A Simple Problem with Integers

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

题意:
区间修改和区间求和

题解:
线段树 + Lzay标记

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

using namespace std;
const int maxn=1e5+100;
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1
typedef long long ll;
ll sum[maxn << 2];
ll lazy[maxn << 2]; 

void pushup(ll root)
{
    sum[root] = sum[root << 1] + sum[root << 1 | 1];
}

void pushdown(ll root, ll ln, ll rn)
{
    if(lazy[root])
        {
            lazy[root << 1] += lazy[root];
            lazy[root << 1 | 1] += lazy[root];

            sum[root << 1] += lazy[root] * ln;
            sum[root << 1 | 1] += lazy[root] * rn;

            lazy[root] = 0;
        }
}

void build(ll left, ll right, ll root)
{
    if(left == right)
        {
            scanf("%lld",&sum[root]);
            return;
        }
    ll mid = left + right >> 1;
    build(lson);
    build(rson);
    pushup(root);
}

ll query(ll left, ll right, ll root, ll L, ll R)
{
    if(L <= left && right <= R)
        {
            return sum[root];
        }

    ll mid = left + right >> 1;
    pushdown(root , mid - left + 1, right - mid);

    ll ans = 0;
    if(L <= mid)
        ans += query(lson, L, R);
    if(R > mid)
        ans += query(rson, L, R);
    return ans;
}

void update(ll left, ll right, ll root, ll L, ll R, ll c)
{
    if(L <= left && right <= R)
        {
            sum[root] += c * (right - left + 1);
            lazy[root] += c;
            return;
        }

    ll mid = left + right >> 1;
    pushdown(root, mid - left + 1, right - mid);

    if(L <= mid)
        update(lson, L, R, c);
    if(R > mid)
        update(rson, L, R, c);

    pushup(root);
}


int main()
{
    ll n, q;
    char op[2];
    scanf("%lld%lld",&n,&q);
    build(1, n, 1);
    while(q--)
        {
            ll l, r;
            ll c;
            scanf("%s",op);
            if(op[0] == 'Q')
                {
                    scanf("%lld%lld",&l,&r);
                    printf("%lld\n",query(1, n, 1, l, r));
                }
            else
                {
                    scanf("%lld%lld%lld",&l,&r,&c);
                    update(1, n, 1, l, r, c);
                }
        }
    return 0;
} 
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注