Poj 3468 线段树 lazy-蒲公英云

Poj 3468 线段树 lazy

女爷i 2022-06-14 04:10 311阅读 0赞

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1 | 1
using namespace std;
typedef long long LL;
const int maxn = 100000+10;
LL add[maxn<<2];
LL sum[maxn<<2];
struct tree {
    int l, r;
    int mid() {
        return (l+r)>>1;
    }
}tr[maxn<<2];
void pushup(int rt) {
    sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt, int m) {
    if (add[rt]) {
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        sum[rt<<1] += 1LL*add[rt]*(m-(m>>1));
        sum[rt<<1|1] += 1LL*add[rt]*(m>>1);
        add[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    tr[rt].l = l;
    tr[rt].r = r;
    add[rt] = 0;
    if (l == r) {
        scanf("%lld", &sum[rt]);
        return ;
    }
    int mid = tr[rt].mid();
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int c, int l, int r, int rt) {
    if (tr[rt].l == l && tr[rt].r == r) {
        add[rt] += c;
        sum[rt] += 1LL*c*(r-l+1);
        return ;
    }
    if (tr[rt].l == tr[rt].r)
        return ;
    pushdown(rt, tr[rt].r-tr[rt].l+1);
    int mid = tr[rt].mid();
    if (r<=mid)
        update(c, l, r, rt<<1);
    else if (l > mid)
        update(c, l, r, rt<<1|1);
    else  {
        update(c, lson);
        update(c, rson);
    }
    pushup(rt);
}
LL query(int l, int r, int rt) {
    if (l == tr[rt].l && tr[rt].r == r) {
        return sum[rt];
    }
    pushdown(rt, tr[rt].r-tr[rt].l+1);
    int mid = tr[rt].mid();
    LL res = 0;
    if (r <= mid)
        res += query(l, r, rt<<1);
    else if (l > mid)
        res += query(l, r, rt<<1|1);
    else {
        res += query(lson);
        res += query(rson);
    }
    return res;
}
int main() {
    int n, q;
    while(~scanf("%d%d", &n, &q)) {
        build(1, n, 1);
        char ch[2];
        while (q--) {
            scanf("%s", ch);
            if (ch[0] == 'C') {
                int l, r, c;
                scanf("%d%d%d", &l, &r, &c);
                update(c, l, r, 1);
            }
            else {
                int l, r;
                scanf("%d%d", &l, &r);
                printf("%lld\n", query(l, r, 1));
            }
        }
    }
    return 0;
}