poj-3468 区间操作

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/42966251

http://poj.org/problem?id=3468

区间求和操作 ，一个区间加操作。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <iomanip>

using namespace std;

#define ll(ind) (ind<<1)
#define rr(ind) (ind<<1|1)
#define Mid(a,b) (a+((b-a)>>1))

typedef __int64 LL;

const int N = 100100;

int a[N];

struct node
{
    int left, right;
    LL sum, lazy;;
    int mid()
    {
        return Mid(left, right);
    }

    void fun(LL summ)
    {
        lazy += summ;
        sum += (right - left + 1) * summ;
    }
};

struct segtree
{
    node tree[N * 4];

    void real(int ind)//更新懒惰标记
    {
        if (tree[ind].lazy)
        {
            tree[ll(ind)].fun(tree[ind].lazy);
            tree[rr(ind)].fun(tree[ind].lazy);
            tree[ind].lazy = 0;
        }
    }

    void buildtree(int left, int right, int ind)//建树
    {
        tree[ind].left = left;
        tree[ind].right = right;
        tree[ind].sum = 0;
        tree[ind].lazy = 0;

        if (left == right)
        {
            tree[ind].sum = a[left];
        }

        if (left != right)
        {
            int mid = tree[ind].mid();
            buildtree(left, mid, ll(ind));
            buildtree(mid + 1, right, rr(ind));
            tree[ind].sum = tree[ll(ind)].sum + tree[rr(ind)].sum;
        }
    }

    void update(int st, int ed, int ind, int type)//更新
    {
        int left = tree[ind].left;
        int right = tree[ind].right;

        if (st <= left && right <= ed)
            tree[ind].fun(type);

        else
        {
            real(ind);

            int mid = tree[ind].mid();
            if (st <= mid) update(st, ed, ll(ind), type);
            if (ed > mid) update(st, ed, rr(ind), type);
            tree[ind].sum = tree[ll(ind)].sum + tree[rr(ind)].sum;
        }
    }

    LL query(int st, int ed, int ind)//求和
    {
        int left = tree[ind].left;
        int right = tree[ind].right;

        if (st <= left && right <= ed)
            return tree[ind].sum;
        else
        {
            real(ind);
            int mid = tree[ind].mid();

            LL s1 = 0, s2 = 0;
            if (st <= mid)
                s1 = query(st, ed, ll(ind));
            if (ed > mid)
                s2 = query(st, ed, rr(ind));

            return s1 + s2;
        }
    }
}seg;

int main()
{
    int n, m;
    int x, y, z;

    while (scanf("%d %d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);

        seg.buildtree(1, n, 1);

        char d[5];

        while (m--)
        {
            scanf("%s", d);
            if (d[0] == 'Q')
            {
                scanf("%d %d", &x, &y);
                cout << seg.query(x, y, 1) << endl;

            }
            else
            {
                scanf("%d %d %d", &x, &y, &z);
                seg.update(x, y, 1, z);
            }
        }
    }
    return 0;
}