UESTC - 1057 秋實大哥與花 線段樹

題意

秋實大哥是一個儒雅之人，晝聽笙歌夜醉眠，若非月下即花前。

是以秋實大哥精心照料了很多花朵。現在所有的花朵排成了一行，每朵花有一個愉悅值。

秋實大哥每天要對着某一段連續的花朵歌唱，然後這些花朵的愉悅值都會增加一個相同的值v(v可能為負)。

同時他想知道每次他唱完歌後這一段連續的花朵的愉悅值總和是多少。

思路

模闆題。

AC代碼

#include <cstdio>
#include <cmath>
#include <cctype>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define pii pair<int, int>
typedef long long LL;
const double PI = acos(-);
const int maxn =  + ;
int a[maxn];

struct node{
    int l, r;
    LL sum, lazy;
    void update(int x) {
        sum += L*(r-l+)*x;
        lazy += x;
    }
}tree[maxn*];

void push_up(int x) {
    tree[x].sum = tree[x<<].sum + tree[x<<|].sum;
}

void push_down(int x) {
    int lazy = tree[x].lazy;
    if(lazy) {
        tree[x<<].update(lazy);
        tree[x<<|].update(lazy);
        tree[x].lazy = ;
    }
}

void build(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    tree[x].sum = tree[x].lazy = ;
    if(l == r) {
        tree[x].sum = a[l];
    }
    else {
        int mid = (l+r) / ;
        build(x<<, l, mid);
        build(x<<|, mid+, r);
        push_up(x);
    }
}

void update(int x, int l, int r, int val) {
    int L = tree[x].l, R = tree[x].r;
    if(l <= L && R <= r) {
        tree[x].update(val);
    }
    else {
        push_down(x);
        int mid = (L+R) / ;
        if(mid >= l) update(x<<, l, r, val);
        if(r > mid) update(x<<|, l, r, val);
        push_up(x);
    }
}

LL query(int x, int l, int r) {
    int L = tree[x].l, R = tree[x].r;
    if(l <= L && R <= r) return tree[x].sum;
    else {
        push_down(x);
        int mid = (L+R) / ;
        LL ans = ;
        if(mid >= l) ans += query(x<<, l, r);
        if(r > mid) ans += query(x<<|, l, r);
        push_up(x);
        return ans;
    }
}

int main() {
    int n, q;
    while(scanf("%d", &n) == ) {
        for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
        build(, , n);
        scanf("%d", &q);
        int l, r, val;
        for(int i = ; i < q; ++i) {
            scanf("%d%d%d", &l, &r, &val);
            update(, l, r, val);
            printf("%lld\n", query(, l, r));
        }
    }
    return ;
}
           

如有不當之處歡迎指出！