[Codevs] 1082 线段树练习3

1082 线段树练习 3

 时间限制: 3 s

 空间限制: 128000 KB

 题目等级 : 大师 Master

 

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数， 

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。 

pascal选手请不要使用readln读入

 

输出描述 Output Description

对于每个询问输出一行一个答案

 

样例输入 Sample Input

3

1 2 3 

2

1 2 3 2

2 2 3

 

样例输出 Sample Output

9

 

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

分析 Analysis

分块！

分块除了细节难调外没有什么问题，，，只要理解到位并且有自己的码风即可。

更具体的分析：

[Codevs] 1081 线段树练习 2 ----“分块！”

代码 Code

#include<cstdio>
#include<iostream>
#include<cmath>
#define maxn 1000000
using namespace std;

long long block[maxn],size,sum[maxn],add[maxn],arr[maxn],n,q,swi;

void modify(){
    long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    a--,b--;
    
    for(long long i = a;i <= min(block[a]*size-1,b);i++)
        arr[i] += c,sum[block[i]] += c;
    if(block[a] != block[b]){
        for(long long i = (block[b]-1)*size;i <= b;i++)
            arr[i] += c;
        sum[block[b]] += (b-(block[b]-1)*size+1)*c;
    }for(long long i = block[a]+1;i < block[b];i++)
        sum[i] += size*c,add[i] += c;
}

void query(){
    long long a,b;
    scanf("%lld%lld",&a,&b);
    a--,b--;
    long long ans = 0;
    
    for(long long i = a;i <= min(block[a]*size-1,b);i++)
        ans += arr[i]+add[block[i]];
    if(block[a] != block[b]){
        for(long long i = (block[b]-1)*size;i <= b;i++)
            ans += arr[i]+add[block[i]];
    }for(long long i = block[a]+1;i < block[b];i++)
        ans += sum[i];
        
    printf("%lld
",ans);
}

int main(){
    scanf("%lld",&n);
    size = (long long)sqrt(n)+1;
    for(long long i = 0;i < n;i++) block[i] = i/size+1;
    for(long long i = 0;i < n;i++) scanf("%lld",&arr[i]);
    for(long long i = 0;i < n;i++) sum[block[i]] += arr[i];
    
    scanf("%lld",&q);
    for(long long i = 0;i < q;i++){
        scanf("%lld",&swi);
        if(swi%2) modify();
        else query();
    }
    
    return 0;
}