首页 > 代码库 > POJ 3468 A Simple Problem with Integers（线段树 区间更新）

POJ 3468 A Simple Problem with Integers（线段树 区间更新）

2024-07-15 20:28:09   233人阅读

Description

You have N integers, A1,A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1,A2, ... , AN. -1000000000 ≤Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa,Aa+1, ... ,Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa,Aa+1, ... ,Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

线段树区间更新。


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define lson o << 1, l, m
#define rson o << 1|1, m+1, r
using namespace std;
typedef long long LL;
const int MAX=0x3f3f3f3f;
const int maxn = 111111;
int n, q, a, b, c;
LL sum[maxn<<2], add[maxn<<2];
void up(int o) {
    sum[o] = sum[o<<1] + sum[o<<1|1];
}
void down(int o, int m) {
    if(add[o] != 0) {
        add[o<<1] += add[o];
        add[o<<1|1] += add[o];
        sum[o<<1] += add[o]*(m-(m>>1));
        sum[o<<1|1] += add[o]*(m>>1);
        add[o] = 0;
    }
}
void build(int o, int l, int r) {
    add[o] = 0;
    if(l == r) scanf("%I64d", &sum[o]);
    else {
        int m = (l+r) >> 1;
        build(lson);
        build(rson);
        up(o);
    }
}
LL query(int o, int l, int r) {
    if(a <= l && r <= b) return sum[o];
    down(o, r-l+1);
    int m = (l+r) >> 1;
    LL ans = 0;
    if(a <= m) ans += query(lson);
    if(m < b) ans += query(rson);
    return ans;
}
void update(int o, int l, int r) {
    if(a <= l && r <= b) {
        add[o] += c;
        sum[o] += (LL)c*(r-l+1);
        return;
    }
    int m = (l+r) >> 1;
    down(o, r-l+1);
    if(a <= m) update(lson);
    if(m < b) update(rson);
    up(o);
}
int main()
{
    scanf("%d%d", &n, &q);
    build(1, 1, n);
    while(q--) {
        char op[3];
        scanf("%s",op);
        if(op[0] == 'C') {
            scanf("%d%d%d", &a, &b, &c);
            update(1, 1, n);
        } else {
            scanf("%d%d", &a, &b);
            printf("%I64d\n", query(1, 1, n));
        }
    }
    return 0;
}





联系
我们