PKU3468区间更新 - c++编程基础

TOP

PKU3468区间更新

2015-07-20 18:00:54 来源: 作者: 【大中小】浏览:3次

Time Limit: 5000MS	?	Memory Limit: 131072K
Total Submissions: 60064	?	Accepted: 18313
Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... , A_N. 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₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
C a b c means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
Q a b means querying the sum of A_a, A_a₊₁, ... , A_b.

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

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #include 
                 
                   #include
                   using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn = 100000 + 10; #define int64 __int64 int64 sum[maxn<<2]; int64 add[maxn<<2]; void PushUp(int64 rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void PushDown(int64 rt,int64 m){ if(add[rt] != 0){ add[rt<<1]+= add[rt]; add[rt<<1|1]+= add[rt]; sum[rt<<1]+=(m-(m>>1))*add[rt]; sum[rt<<1|1]+=(m>>1)*add[rt]; add[rt] = 0; } } void build(int64 l,int64 r,int64 rt){ add[rt] = 0; if(l == r){ scanf(%I64d,&sum[rt]); return ; } int64 m = (l+r)/2; build(lson); build(rson); PushUp(rt); } void update(int64 L,int64 R,int64 c,int64 l,int64 r,int64 rt){ if(L<=l && r<=R){ add[rt]+= c; sum[rt] = sum[rt]+(r-l+1)*c; return ; } PushDown(rt,r-l+1); int64 m = (l+r)/2; if(L <= m){ update(L,R,c,lson); } if(R > m){ update(L,R,c,rson); } PushUp(rt); } int64 query(int64 L,int64 R,int64 l,int64 r,int64 rt){ if(L<=l && r<=R){ return sum[rt]; } PushDown(rt,r-l+1);//因为这是区间更新，所以不一定要到最底层才进行更新，所以每段区间的和要返回到子节点，而单点更新一定是到最底层的所以不需要返回到子节点 int64 ret = 0; int64 m = (l+r)/2; if(L <= m){ ret+=query(L,R,lson); } if(R > m){ ret+=query(L,R,rson); } return ret; } int main(){ int64 n,m; char s[20]; int64 x,y,z; while(~scanf(%I64d%I64d,&n,&m)){ build(1,n,1); while(m--){ scanf(%s,s); if(s[0] == 'C'){ scanf(%I64d%I64d%I64d,&x,&y,&z); update(x,y,z,1,n,1); } else{ scanf(%I64d%I64d,&x,&y); printf(%I64d ,query(x,y,1,n,1)); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVa514 Rails（铁轨）	下一篇：HDU - 1698 Just a Hook （线段树..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: