1 条题解
-
1チルノ (9Cirno) LV 7 MOD Baka tayz @ 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