POJ 3468 A Simple Problem with Integers

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100001;
int n, q, l, r, c, a[N << 2];
char ch;
LL d[N << 2], b[N << 2];
void build(int p, int s, int t) {
    if (s == t) {
        d[p] = a[s];
        return;
    }
    int m = s + t >> 1;
    build(p * 2, s, m), build(p * 2 + 1, m + 1, t);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
void update(int p, LL c, int l, int r, int s, int t) {
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c, b[p] += c;
        return;
    }
    int m = t + s >> 1;
    if (b[p] && s != t) {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    if (l <= m) update(p * 2, c, l, r, s, m);
    if (r > m) update(p * 2 + 1, c, l, r, m + 1, t);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
LL getSum(int p, int l, int r, int s, int t) {
    if (l <= s && t <= r) return d[p];
    int m = s + t >> 1;
    if (b[p]) {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    LL sum = 0;
    if (l <= m) sum = getSum(p * 2, l, r, s, m);
    if (r > m) sum += getSum(p * 2 + 1, l, r, m + 1, t);
    return sum;
}
int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 0; i < q; ++i) {
        getchar();
        scanf("%c %d %d", &ch, &l, &r);
        if (ch == 'Q') {
            printf("%lld\n", getSum(1, l, r, 1, n));
        } else {
            scanf("%d", &c);
            update(1, c, l, r, 1, n);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100001;
int n, q, l, r, c, a[N], L[N], R[N], pos[N];
LL sum[N], add[N];
char ch;
void build() {
    int t = sqrt(n * 1.0);
    int num = n / t;
    if (n % t) ++num;
    for (int i = 1; i <= num; ++i)
        L[i] = (i - 1) * t + 1, R[i] = i * t;
    R[num] = n;
    for (int i = 1; i <= num; ++i)
        for (int j = L[i]; j <= R[i]; ++j)
            pos[j] = i, sum[i] += a[j];
}
void change(int l, int r, int d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; ++i) a[i] += d;
        sum[p] += d * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; ++i) add[i] += d;
        for (int i = l; i <= R[p]; ++i) a[i] += d;
        sum[p] += d * (R[p] - l + 1);
        for (int i = L[q]; i <= r; ++i) a[i] += d;
        sum[q] += d * (r - L[q] + 1);
    }
}
LL query(int l, int r) {
    int p = pos[l], q = pos[r];
    LL ans = 0;
    if (p == q) {
        for (int i = l; i <= r; ++i) ans += a[i];
        ans += add[p] * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; ++i)
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; ++i) ans += a[i];
        ans += add[p] * (R[p] -l + 1);
        for (int i = L[q]; i <= r; ++i) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}
int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build();
    for (int i = 0; i < q; ++i) {
        getchar();
        scanf("%c %d %d", &ch, &l, &r);
        if (ch == 'Q') {
            printf("%lld\n", query(l, r));
        } else {
            scanf("%d", &c);
            change(l, r, c);
        }
    }
    return 0;
}