BZOJ 3212: A Simple Problem with Integers – [线段树]


题目传送门(BZOJ)

题解 :

线段树, 区间加, 区间求和
注意文末提示可能爆int, 我以为保证不爆int所以竟然还 WA 惹

代码 :

#include 
#include 
#include 
#include 
#define ls p << 1
#define rs p << 1|1
#define ll long long
using namespace std;
const int N = 100010;
ll t[N<<2], laz[N<<2];
int a[N];
void build(int l, int r, int p) {
    if(l == r) return t[p] = a[l], void();
    int mid = (l+r) >> 1;
    build(l, mid, ls); build(mid+1, r, rs);
    t[p] = t[ls]+t[rs];
}
inline void pd(int l, int r, int p) {
    if(laz[p]) {
        int mid = (l+r) >> 1;
        laz[ls] += laz[p], laz[rs] += laz[p];
        t[ls] += ((ll)mid-l+1)*laz[p];
        t[rs] += ((ll)r-mid)*laz[p];
        laz[p] = 0;
    }
}
ll query(int l, int r, int p, int x, int y) {
    if(x <= l && y >= r) return t[p];
    pd(l, r, p);
    int mid = (l+r) >> 1;
    ll ret = 0;
    if(x <= mid) ret = query(l, mid, ls, x, y);
    if(y >  mid) ret += query(mid+1, r, rs, x, y);
    return ret;
}
void change(int l, int r, int p, int x, int y, int c) {
    if(x <= l && y >= r) {
        t[p] += ((ll)r-l+1)*c;
        laz[p] += c;
        return ;
    }
    pd(l, r, p);
    int mid = (l+r) >> 1;
    if(x <= mid) change(l, mid, ls, x, y, c);
    if(y >  mid) change(mid+1, r, rs, x, y, c);
    t[p] = t[ls]+t[rs];
}
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    build(1, n, 1);
    for(int i = 1; i <= m; i ++ ) {
        int x, y, c;
        char opt[3]; scanf("%s%d%d", opt, &x, &y);
        if(opt[0] == 'Q') {
            printf("%lld\n", query(1, n, 1, x, y));
        }
        else {
            scanf("%d", &c);
            change(1, n, 1, x, y, c);
        }
    }
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注