#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAXN 100050

__int64 tree[MAXN * 4], lazyAdd[MAXN * 4];

inline void PushUp(int node)
{
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void PushDown(int node, __int64 length)
{
    if (lazyAdd[node])// *******如果是if (lazyAdd[node] > 0)就会WA！！
    {
        tree[node * 2] += lazyAdd[node] * (length - length / 2);
        tree[node * 2 + 1] += lazyAdd[node] * (length / 2);

        lazyAdd[node * 2] += lazyAdd[node];
        lazyAdd[node * 2 + 1] += lazyAdd[node];

        lazyAdd[node] = 0;
    }
}

void BuildSegmentTree(int node, int l, int r)
{
    lazyAdd[node] = 0;
    if (l == r)
    {
        scanf("%I64d", &tree[node]);
    }
    else
    {
        int m = (l + r) / 2;
        BuildSegmentTree(node * 2, l, m);
        BuildSegmentTree(node * 2 + 1, m + 1, r);
        PushUp(node);
    }
}

__int64 Query(int node, int cl, int cr, int ql, int qr)
{
    if (ql <= cl && cr <= qr)
    {
        return tree[node];
    }

    PushDown(node, cr - cl + 1);
    int m = (cl + cr) / 2;
    __int64 sum = 0;
    if (ql <= m) sum += Query(node * 2, cl, m, ql, qr);
    if (qr > m) sum += Query(node * 2 + 1, m + 1, cr, ql, qr);

    return sum;
}

void Update(int node, int cl, int cr, int ql, int qr, __int64 add)
{
    __int64 length = cr - cl + 1;
    if (ql <= cl && cr <= qr)
    {
        tree[node] += add * length;
        lazyAdd[node] += add;
    }
    else
    {
        PushDown(node, length);
        int m = (cl + cr) / 2;
        if (ql <= m) Update(node * 2, cl, m, ql, qr, add);
        if (qr > m) Update(node * 2 + 1, m + 1, cr, ql, qr, add);

        PushUp(node);
    }
}

int main()
{
    char op[2];
    int n, q, a, b, c;
    scanf("%d %d", &n, &q);
    BuildSegmentTree(1, 1, n);
    while (q--)
    {
        scanf("%s", op);
        if (op[0] == 'C')
        {
            scanf("%d %d %d", &a, &b, &c);
            Update(1, 1, n, a, b, c);
        }
        else
        {
            scanf("%d %d", &a, &b);
            printf("%I64d\n", Query(1, 1, n, a, b));
        }
    }

    return 0;
}

• lazy 可以小于0的。 (0) LeZeon 2015-07-23 14:01:01