【洛谷P3372】【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例#1：

5 5

1 5 4 2 3

2 2 4

1 2 3 2

2 3 4

1 1 5 1

2 1 4

输出样例#1：

11

8

20

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^，保证在int64/long long数据范围内）

样例说明：

题解

沉迷线段树无法自拔

记下这个代码，以后省选会用

总体思想就是维护两个线段树，一个存对应区间每一个数加的值，一个存对应区间每一个数的和（不包括区间每一个数都要加的值）

更新时如果要加区间全部包含当前区间则第一个线段树对应区间+=x

否则第二个线段树+=(min(b,r)-max(a,l))*x，之后递归。

具体实现见下（PS：一定要用long long）

My Code

（调试代码感人）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll dt[],dtb[];
int n,m;
ll itmp[];
void init(int k,int l,int r) {
    if(r-l==) {
        dtb[k]=itmp[l];
        //printf("%d %d\n",l,r);
    } else {
        //printf("%d %d\n",l,r);
        int chl=k*2,chr=k*2+;
        init(chl,l,(l+r)/);
        init(chr,(l+r)/,r);
        dtb[k]=dtb[chl]+dtb[chr];
        //printf("%d %d %d %d\n",dt[k],l,(l+r)/,r);
    }
}
void add(int a,int b,ll x,int k,int l,int r) {
    if(a<=l&&r<=b){
        dt[k]+=x;   
    }else if(l<b&&a<r){
    dtb[k]+=((ll)min(b,r)-(ll)max(a,l))*x;
    int chl=k*2,chr=k*2+;
//  printf("%d %d\n",l,r);gouliguojiashengsiyi,qiyinhuofubiquzhi
    add(a,b,x,chl,l,(l+r)/);
    add(a,b,x,chr,(l+r)/,r);
    }  
}
ll query(int a,int b,int k,int l,int r) {
    if(b<=l||r<=a)return ;
    if(a<=l&&r<=b) {
        //printf("%d %d\n",k,dt[k]);
        return dt[k]*(ll)(r-l)+dtb[k];
    }  
    if(r-l!=){
        int chl=k*2,chr=k*2+;
        ll res=dt[k]*((ll)min(b,r)-(ll)max(a,l));
        res+=query(a,b,chl,l,(l+r)/);
        res+=query(a,b,chr,(l+r)/,r);

        //printf("%d %d %d %d\n",res,l,(l+r)/,r);
        return res;
    }
}
int main() {
        memset(dt,,sizeof(dt));
        memset(dtb,,sizeof(dtb));
        memset(itmp,,sizeof(itmp));
        scanf("%d%d",&n,&m);
        for(int i=; i<=n; i++) {
            scanf( "%lld",&itmp[i]);
        }
        init(,,n+);
        int tp,x,y; 
        for(int i=;i<=m;i++) {
            scanf("%d%d",&tp,&x);
            if(tp==) {
                printf("%lld\n",query(x,x+,,,n+));
            }
            if(tp==) {
                ll z;
                scanf("%d%lld",&y,&z);
                add(x,y+,z,,,n+);
            }
        }
    return ;
}