POJ 3468 A Simple Problem with Integers （线段树---区间更新）

朴灿烈づ我的快乐病毒、 2024-02-17 21:10 15阅读 0赞

A Simple Problem with Integers

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

分析：线段树之区间更新，根据区间更新模板就可以很容易的写出来

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long LL;
    const int maxn=1e5+10;
    LL sum[maxn<<2];
    LL cnt[maxn<<2];  //延迟标记 
    int N,Q;
    
    void build(int l,int r,int rt){
    	cnt[rt]=0;
    	if(l==r){
    	  scanf("%lld",&sum[rt]);  //输入时注意lld，没注意到WA了一次 
    	  return ;	
    	}
    	
    	int m=(l+r)>>1;
    	build(l,m,rt<<1);
    	build(m+1,r,rt<<1|1);
    	sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 
    } 
    
    void Down(int rt,int len){
       if(cnt[rt]){
       	cnt[rt<<1]+=cnt[rt];
       	cnt[rt<<1|1]+=cnt[rt];
       	sum[rt<<1]+=cnt[rt]*(len-(len>>1));
       	sum[rt<<1|1]+=cnt[rt]*(len>>1);
       	cnt[rt]=0;
       }	
    }
    
    LL Query(int a,int b,int l,int r,int rt){
    	if(a<=l && b>=r){
    		return sum[rt];
    	}
    	
    	Down(rt,r-l+1);
    	int m=(l+r)>>1;
    	LL ans=0;
    	if(a<=m)
    	  ans+=Query(a,b,l,m,rt<<1);
    	if(b>m)
    	  ans+=Query(a,b,m+1,r,rt<<1|1);
    	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    	return ans; 
    }
    
    
    void Update(int a,int b,int c,int l,int r,int rt){
    	if(a<=l && b>=r){
    		cnt[rt]+=c;
    		sum[rt]+=(LL)(r-l+1)*c;
    		return ;
    	}
    	
    	Down(rt,r-l+1);
    	int m=(r+l)>>1;
    	if(a<=m)
    	 Update(a,b,c,l,m,rt<<1);
    	if(b>m) 
    	 Update(a,b,c,m+1,r,rt<<1|1);
    	 
    	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    
    int main(){
    	while(scanf("%d%d",&N,&Q)==2){
    		build(1,N,1);
    		
    		for(int i=0;i<Q;i++){
    			char ch;
    			int a,b,c;
    			getchar();
    			scanf("%c",&ch);
    			if(ch=='Q'){
    				scanf("%d%d",&a,&b);
    				LL ans=Query(a,b,1,N,1);
    				printf("%lld\n",ans);
    			}
    			else {
    				scanf("%d%d%d",&a,&b,&c); 
    				Update(a,b,c,1,N,1);
    			}
    		}
    		
    	}
    	return 0;
    }