线段树（更新区间查询区间）poj 3468 A Simple Problem with Integers

痛定思痛。 2022-06-07 01:46 183阅读 0赞

题目链接：http://poj.org/problem?id=3468

A Simple Problem with Integers

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;131072K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;119447</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;37100</td> 
  </tr> 
  <tr> 
   <td colspan="3" align="center" style="color:rgb(14,173,0)"><strong>Case Time Limit:</strong>&nbsp;2000MS</td> 
  </tr> 
 </tbody> 
</table>

Description

You have *N* integers, *A*1, *A*2, ... , *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 *A*1, *A*2, ... , *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

[POJ Monthly--2007.11.25][], Yang Yi

代码：

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    #define N 100000+10
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    ll sum[N<<2],add[N<<2];
    struct Node
    {
        int l,r;
        int mid()
        {
            return (l+r)>>1;
        }
    }tree[N<<2];
    void PushUp(int rt)
    {
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    
    void build(int l,int r,int rt)
    {
        tree[rt].l=l;
        tree[rt].r=r;
        add[rt]=0;
        if(l==r)
        {
            scanf("%I64d",&sum[rt]);
            return;
        }
        int m=tree[rt].mid();
        build(lson);
        build(rson);
        PushUp(rt);
    }
    void PushDown(int rt,int m)
    {
        if(add[rt])
        {
            add[rt<<1]+=add[rt];
            add[rt<<1|1]+=add[rt];
            sum[rt<<1]+=add[rt]*(m-(m>>1));
            sum[rt<<1|1]+=add[rt]*(m>>1);
            add[rt]=0;
        }
    }
    ll query(int l,int r,int rt)
    {
        if(l==tree[rt].l&&r==tree[rt].r)
        {
            return sum[rt];
        }
        PushDown(rt,tree[rt].r-tree[rt].l+1);
    
        int m=tree[rt].mid();
        ll res=0;
        if(r<=m)
        {
            res+=query(l,r,rt<<1);
        }
        else if(l>m)
        {
            res+=query(l,r,rt<<1|1);
        }
        else
        {
            res+=query(l,m,rt<<1);
            res+=query(rson);
        }
        return res;
    }
    void update(int c,int l,int r,int rt)
    {
        if(tree[rt].l==l&&tree[rt].r==r)
        {
            add[rt]+=c;
            sum[rt]+=(ll)c*(r-l+1);
            return ;
        }
       
        PushDown(rt,tree[rt].r-tree[rt].l+1);
        int m=tree[rt].mid();
        if(r<=m)
        {
            update(c,l,r,rt<<1);
        }
        else if(l>m)
        {
            update(c,l,r,rt<<1|1);
        }
        else
        {
            update(c,l,m,rt<<1);
            update(c,m+1,r,rt<<1|1);
        }
        PushUp(rt);
    }
    int main()
    {
        int n,m;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            build(1,n,1);
            while(m--)
            {
                char ch[2];
                scanf("%s",ch);
                int a,b,c;
                if(ch[0]=='Q')
                {
                    scanf("%d%d",&a,&b);
                    printf("%lld\n",query(a,b,1));
                }
                else
                {
                    scanf("%d%d%d",&a,&b,&c);
                    update(c,a,b,1);
                }
            }
        }
        return 0;
    }

[POJ Monthly--2007.11.25]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2007.11.25