POJ--3468 A Simple Problem with Integers(线段树/树状数组)

57one / 2024-02-25 / 原文

记录
11:03 2024-2-25

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

线段树
树状数组

把区间增加转变为单点增加，利用两个树状数组$c_0 和 c_1$
将”C l r d" 转化为

在树状数组$c_0$中，把位置l上的数加d
在树状数组$c_0$中，把位置r + 1上的数减d
在树状数组$c_1$中，把位置l上的数加l * d
在树状数组$c_1$中，把位置r + 1上的数减(r + 1) * d

建立sum存储a的原始前缀和
将“Q l r” 转化为 1~r 和 1~l-1两部分进行相减
$ (sum[r] + (r + 1) * ask(c_0, r) - ask(c_1, r)) - (sum[l - 1] + l * ask(c_0, l - 1) - ask(c_1, l - 1)) $

点击查看代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

const int MAXN = 100005;
int N, Q;
ll a[MAXN], sum[MAXN];
ll c[2][MAXN];

// k表示是哪个树状数组，i表示位置, v表示加入的值
void add(int k, int i, int v) {
    while (i <= N){
        c[k][i] += v;
        i += i & -i;
    }
}

// k表示是哪个树状数组，i表示位置
ll ask(int k, int i) {
    ll s = 0;
    while (i > 0) {
        s += c[k][i];
        i -= i & -i;
    }
    return s;
}

int main() {
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) {
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    char c[2];
    int l, r, v;
    for(int i = 0; i < Q; i++) {
        // %s 它会读入一个不含空格、TAB和回车符的字符串，存入字符数组
        // %c 会读入\n
        scanf("%s%d%d", c, &l, &r);
        if(c[0] == 'C') {
            scanf("%d", &v);
            add(0, l, v);
            add(0, r + 1, -v);
            add(1, l, l * v);
            add(1, r + 1, -(r + 1) * v);
        } else {
            ll result = (sum[r] + (r + 1) * ask(0, r) - ask(1, r))
                        - (sum[l - 1] + l * ask(0, l - 1) - ask(1, l - 1));
            printf("%lld\n", result);
        }
    }
}