P3372 【模板】线段树 1

提交记录

代码是 $n^{\frac{1}{3}}$ 的分块。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define fil [[gnu::always_inline]] inline
#define up(i,l,r) for(long long i=(l),E##i=(r);i<=E##i;++i)
#define dn(i,r,l) for(long long i=(r),E##i=(l);i>=E##i;--i)
using namespace std; namespace gce = __gnu_cxx;
typedef long long ll; namespace pbds = __gnu_pbds;
constexpr ll N1 = 50, N2 = N1 * N1, N3 = N2 * N1;

ll n;
array < ll, N1 + 5 > c, ct, cl, cr;
array < ll, N2 + 5 > b, bm, bt, bl, br; // 和 上级块 标记 左边界 右边界
array < ll, N3 + 5 > a, am;

fil void build() {
    up (k, 1, N1) {
        cl[k] = cr[k - 1] + 1;
        cr[k] = k * N1;
        up (j, cl[k], cr[k]) {
            bl[j] = br[j - 1] + 1;
            br[j] = j * N1;
            up (i, bl[j], br[j]) {
                am[i] = j;
                b[j] += a[i];
            }
            bm[j] = k;
            c[k] += b[j];
        }
    }
}

inline namespace add_meth {

    fil void addc(ll p, ll q, ll w) {
        assert(p - q <= 1);

        up (k, p, q) c[k] += w * N2, ct[k] += w;
    }

    fil void addb(ll x, ll y, ll w) {
        // OK: assert(x - y <= 1);

        up (j, x, y) b[j] += w * N1, bt[j] += w;
        c[bm[x]] += (y - x + 1) * N1 * w;
    }

    fil void adda(ll l, ll r, ll w) {
        // OK: assert(l <= r);

        up (i, l, r) a[i] += w;
        b[am[l]] += (r - l + 1) * w;
    }

    fil void add(ll l, ll r, ll w) {

        ll x = am[l], y = am[r];
        if (x == y) return adda(l, r, w);
        adda(l, br[x], w); adda(bl[y], r, w);
        ++x; --y; if (x > y) return;

        ll p = bm[x], q = bm[y];
        if (p == q) return addb(x, y, w);
        addb(x, cr[p], w); addb(cl[q], y, w);
        ++p; --q;

        return addc(p, q, w);
    }
}

inline namespace sum_meth {

    fil void sumc(ll p, ll q, ll& w) {
        assert(p - q <= 1);

        up (k, p, q) w += c[k];
    }

    fil void sumb(ll x, ll y, ll& w) {
        // OK: assert(x - y <= 1);

        up (j, x, y) w += b[j];
        w += (y - x + 1) * N1 * ct[bm[x]];
    }

    fil void suma(ll l, ll r, ll& w) {
        // OK: assert(l <= r);

        up (i, l, r) w += a[i];
        w += (r - l + 1) * bt[am[l]];
    }

    fil void sum(ll l, ll r, ll &w) {
        w = 0;

        ll x = am[l], y = am[r];
        if (x == y) return suma(l, r, w);
        suma(l, br[x], w); suma(bl[y], r, w);
        ++x; --y; if (x > y) return;

        ll p = bm[x], q = bm[y];
        if (p == q) return sumb(x, y, w);
        sumb(x, cr[p], w); sumb(cl[q], y, w);
        ++p; --q;

        return sumc(p, q, w);
    }
}

int main() {
    ll q, tp, l, r, k;
    cin >> n >> q;
    up(i, 1, n) cin >> a[i];
    build();
    while (q--) {
        cin >> tp >> l >> r;
        if (tp == 1) {
            cin >> k;
            add(l, r, k);
        } else {
            sum(l, r, k);
            cout << k << endl;
        }
    }
}