Poj 3468 线段树 lazy

女爷i 2022-06-14 04:10 227阅读 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;
    }