poj 3468 A Simple Problem with Integers 【线段树-成段更新】

我不是女神ヾ 2022-08-13 14:43 15阅读 0赞

题目：[poj 3468 A Simple Problem with Integers][]

题意：给出n个数，两种操作

1：l -- r 上的所有值加一个值val

2：求l---r 区间上的和

分析：线段树成段更新，成段求和

树中的每个点设两个变量sum 和 num ，分别保存区间 l--r 的和 和l---r 每个值要加的值

对于更新操作：对于要更新到的区间上面的区间，直接进行操作 加上 （r - l +1）\* val 。下面的区间标记num += val

对于求和操作，每次进行延迟更新，把num值分别更新到两个子区间，sum值更新，然后num值变为0

注意：这个题目会超int 。所以

AC代码：

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <math.h>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const long long N = 110000;
    const long long inf = 0x3f3f3f3f;
    struct Node
    {
        long long l,r;
        long long num,sum;
    };
    Node tree[5*N];
    long long a[N];
    long long cnt ;
    void build(long long o,long long l,long long r)
    {
        tree[o].l = l,tree[o].r = r;
        tree[o].num = 0;
        if(l==r)
        {
            tree[o].sum = a[cnt++];
            return ;
        }
        long long mid = (l+r)/2;
        build(o+o,l,mid);
        build(o+o+1,mid+1,r);
        tree[o].sum = tree[o+o].sum + tree[o+o+1].sum;
    }
    void push_update(long long o)
    {
        if(tree[o].num!=0)
        {
            tree[o].sum += tree[o].num * (tree[o].r-tree[o].l+1);
            tree[o+o+1].num += tree[o].num;
            tree[o+o].num += tree[o].num;
            tree[o].num = 0;
        }
    }
    void update(long long o,long long l,long long r,long long val)
    {
        if(l==tree[o].l && r == tree[o].r)
        {
            tree[o].num += val;
            return ;
        }
        tree[o].sum += (val*(r-l+1)); //维护前面的
        long long mid = (tree[o].l+tree[o].r) / 2;
        if(r<=mid)
            update(o+o,l,r,val);
        else if(l>mid)
            update(o+o+1,l,r,val);
        else
        {
            update(o+o,l,mid,val);
            update(o+o+1,mid+1,r,val);
        }
    }
    long long query(long long o,long long l,long long r)
    {
        if(tree[o].l==l && tree[o].r == r)
        {
            return tree[o].sum+(r-l+1)*tree[o].num;
        }
        push_update(o); //维护后面的
        long long mid = (tree[o].l+tree[o].r)/2;
        if(r<=mid)
            return query(o+o,l,r);
        else if(l>mid)
            return query(o+o+1,l,r);
        else
            return query(o+o,l,mid) + query(o+o+1,mid+1,r);
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        long long n,m;
        while(~scanf("%lld%lld",&n,&m))
        {
            cnt = 0;
            for(long long i=0;i<n;i++)
                scanf("%lld",&a[i]);
            build(1,1,n);
            while(m--)
            {
                getchar();
                char c;
                long long x,y;
                scanf("%c",&c);
                scanf("%lld%lld",&x,&y);
                //printf("*****************************************\n");
                if(c=='Q')
                {
                    printf("%lld\n",query(1,x,y));
                }
                else
                {
                    long long val;
                    scanf("%lld",&val);
                    update(1,x,y,val);
                }
            }
        }
        return 0;
    }

[poj 3468 A Simple Problem with Integers]: http://poj.org/problem?id=3468