【洛谷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 ;
}