1 条题解

  • 1
    @ 2024-04-18 19:01:00

    省流:线段树板子

    #include <cstdio>
    
    #define MAXN 100010
    #define ll long long
    #define ls(p) p << 1
    #define rs(p) p << 1 | 1
    
    namespace Cirno {
        ll n, m;
        ll a[MAXN];
    
        struct  SegmentTree {
            ll tree[MAXN << 2];
            ll lazy[MAXN << 2];
    
            inline void PushUp(ll p) {
                tree[p] = tree[ls(p)] + tree[rs(p)];
            }
    
            inline void Build(ll p, ll l, ll r) {
                if (l == r) {
                    tree[p] = a[l];
                    return ;
                }
                ll mid = (l + r) >> 1;
                Build(ls(p), l, mid);
                Build(rs(p), mid + 1, r);
                PushUp(p);
            }
    
            inline void AddLazy(ll p, ll l, ll r, ll k) {
                lazy[p] += k;
                tree[p] += k * (r - l + 1);
            }
    
            inline void PushDown(ll p, ll l, ll r) {
                if (lazy[p]) {
                    ll mid = (l + r) >> 1;
                    AddLazy(ls(p), l, mid, lazy[p]);
                    AddLazy(rs(p), mid + 1, r, lazy[p]);
                    lazy[p] = 0;
                }
            }
    
            inline void Update(ll L, ll R, ll p, ll l, ll r, ll k) {
                if (L <= l && R >= r) {
                    AddLazy(p, l, r, k);
                    return;
                }
                PushDown(p, l, r);
                ll mid = (l + r) >> 1;
                if (L <= mid) Update(L, R, ls(p), l, mid, k);
                if (R > mid) Update(L, R, rs(p), mid + 1, r, k);
                PushUp(p);
            }
    
            inline ll Query(ll L, ll R, ll p, ll l, ll r) {
                if (L <= l && R >= r) return tree[p];
                PushDown(p, l, r);
                ll mid = (l + r) >> 1;
                ll res = 0;
                if (L <= mid) res += Query(L, R, ls(p), l, mid);
                if (R > mid) res += Query(L, R, rs(p), mid + 1, r);
                return res;
            }
        } Tree;
    
        inline void init() {
            scanf("%lld %lld", &n, &m);
            for (int i = 1; i <= n; i++)
                scanf("%lld", &a[i]);
        }
    
        inline void Solve() {
            init();
            Tree.Build(1, 1, n);
            while (m--) {
                ll opt, l, r, k;
                scanf("%lld", &opt);
                if (opt == 1) {
                    scanf("%lld %lld %lld", &l, &r, &k);
                    Tree.Update(l, r, 1, 1, n, k);
                } else {
                    scanf("%lld %lld", &l, &r);
                    ll ans = Tree.Query(l, r, 1, 1, n);
                    printf("%lld %lld\n", ans, (ans << 1) + (ans << 2));
                }
            }
        }
    }
    
    int main () {
        Cirno::Solve();
        return 0;
    }
    
  • 1

原始人,启动 / 【模板】线段树

信息

ID
1003
难度
9
分类
线段树 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者