萌新30pts分块求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr int N = 8e5 + 1, SQ = sqrt(N);

int n, m;
ll sum[SQ + 5], add[SQ + 5], t, siz, st[SQ + 5], ed[SQ + 5], pos[SQ + 5], a[N];

void updata(int L, int R, ll k) {
    int p = pos[L], q = pos[R];
    if (p == q) {
        for (int i = L; i <= R; ++i) a[i] += k;
        sum[p] += (R - L + 1) * k;
        return ;
    }
    for (int i = p + 1; i <= q - 1; ++i) add[i] += k;

    for (int i = L; i <= ed[p]; ++i) a[i] += k;
    sum[p] += (ed[p] - L + 1) * k;
    for (int i = st[q]; i <= R; ++i) a[i] += k;
    sum[q] += k * (R - st[q] + 1);
}

ll query(int L, int R) {
    int p = pos[L], q = pos[R];
    ll res = 0;
    if (p == q) {
        for (int i = L; i <= R; ++i) res += a[i] + add[pos[i]];
        return res;
    }
    for (int i = p + 1; i < q; ++i) res += sum[i] + add[i] * (ed[p] - st[p] + 1);
    for (int i = L; i <= ed[p]; ++i) res += a[i] + add[p];
    for (int i = st[q]; i <= R; ++i) res += a[i] + add[q];
    return res;
}

int main() {
//  freopen("P3372_4.in","r",stdin);
//  freopen("T.out","w",stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    siz = sqrt(n);
    t = n % siz == 0 ? n / siz : n / siz + 1;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= t; ++i) {
        st[i] = (i - 1) * siz + 1;
        ed[i] = i * siz;
    }
    ed[t] = n;
    for(int i=1;i<=t;++i) {
        for(int j=st[i];j<=ed[i];++j) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    while (m--) {
        ll opt, x, y, k;
        cin >> opt;
        if (opt == 1) {
            cin >> x >> y >> k;
            updata(x, y, k);
        } else {
            cin >> x >> y;
            cout << query(x, y) << '\n';
        }
    }
    return 0;
}