某島

… : "…アッカリ~ン . .. . " .. .
July 17, 2011

POJ 3468. A Simple Problem with Integers

Brief description:

區間修改(+-d,區間求和的例題。

Analysis:

略)。。S[x] 表示和 (Sum 。。D[x] 表示作用在 x 結點區間上的修改操作,延遲下放標記。。(Delay
。。這類標記可以在打上去的時候就已經作用在 S[x] 上(完成時。。。
或者在下放之後才作用在 S[x] 上。。(未完成時。。。

。。線段樹。。(完成時標記。。
。。線段樹。。(未完成時標記。。

… (貌似區別不大 ? 。(。注意使用完成時標記修改時必須下放。。。
。。(其實我是來記錄巨神犇的樹狀數組方法的。。。 /$:Orz )

const int N = 100009;

LL B[N], C[N];
// Binary Index Tree
int n, m, a, b, d; char c;

LL Sum(int x){
    LL s1 = 0, s2 = 0, t = n - x; while (x <= n) s1 += B[x], s2 += C[x], x += low_bit(x);
    return s1 * t - s2;
}

void Add(int x, int d){
    LL t = (LL) (n - x - 1) * d;
    while (x) B[x] += d, C[x] += t, x ^= low_bit(x);
}

LL Sum(int l, int r){
    return Sum(l) - Sum(r+1);
}

void Add(int l, int r, int d){
    Add(r, d), Add(l-1, -d);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, m); REP_1(i, n) Add(i, i, RD());

    DO(m){
        RC(c), RD(a, b);
        if (c == 'C') Add(a, b, RD());
        else OT(Sum(a, b));
    }
}
LL Sum(int x){
    LL s1 = 0, s2 = 0, t = x; while (x) s1 += B[x], s2 += C[x], x ^= low_bit(x);
    return s1 * t - s2;
}

void Add(int x, int d){
    LL t = (LL) (x - 1) * d;
    while (x <= n) B[x] += d, C[x] += t, x += low_bit(x);
}

LL Sum(int l, int r){
    return Sum(r) - Sum(l-1);
}

void Add(int l, int r, int d){
    Add(l, d), Add(r+1, -d);
}

External link:

http://poj.org/problem?id=3468