题解 | #数据结构#

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
#define ls(p) p << 1
#define rs(p) p << 1 | 1
const int N = 1e4 + 8;
ll a[N], sum[N << 2], tot[N << 2], lz[N << 2], la[N << 2];
void build(int p, int l, int r)
{
    la[p] = 1;
    if(l == r)
    {
        sum[p] = a[l], tot[p] = a[l] * a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(ls(p), l, m);
    build(rs(p), m + 1, r);
    sum[p] = sum[ls(p)] + sum[rs(p)];
    tot[p] = tot[ls(p)] + tot[rs(p)];
}

void pushDown(int p, int pl, int pr)
{
    if(la[p])
    {
        la[ls(p)] *= la[p];
        la[rs(p)] *= la[p];
        lz[ls(p)] *= la[p];
        lz[rs(p)] *= la[p];
        sum[ls(p)] *= la[p];
        sum[rs(p)] *= la[p];
        tot[ls(p)] *= la[p] * la[p];
        tot[rs(p)] *= la[p] * la[p];
        la[p] = 1;
    }
    if(lz[p])
    {
        int m = (pl + pr) >> 1;
        tot[ls(p)] += 2 * lz[p] * sum[ls(p)] + lz[p] * lz[p] * (m - pl + 1);
        tot[rs(p)] += 2 * lz[p] * sum[rs(p)] + lz[p] * lz[p] * (pr - m);
        lz[ls(p)] += lz[p];
        lz[rs(p)] += lz[p];
        sum[ls(p)] += lz[p] * (m - pl + 1);
        sum[rs(p)] += lz[p] * (pr - m);
        lz[p] = 0;
    }
}
void add(int p, int l, int r, int pl, int pr, ll d)
{
    if(pl >= l && pr <= r)
    {
        lz[p] += d;
        tot[p] += 2 * d * sum[p] + d * d * (pr - pl + 1);
        sum[p] += d * (pr - pl + 1);
        return;
    }
    pushDown(p, pl, pr);
    int m = (pl + pr) >> 1;
    if(l <= m) add(ls(p), l, r, pl, m, d);
    if(r > m) add(rs(p), l, r, m + 1, pr, d);
    sum[p] = sum[ls(p)] + sum[rs(p)];
    tot[p] = tot[ls(p)] + tot[rs(p)];
}
void mul(int p, int l, int r, int pl, int pr, ll d)
{
    if(pl >= l && pr <= r)
    {
        la[p] *= d;
        lz[p] *= d;
        sum[p] *= d;
        tot[p] *= d * d;
        return;
    }
    pushDown(p, pl, pr);
    int m = (pl + pr) >> 1;
    if(l <= m) mul(p, l, r, pl, m, d);
    if(r > m) mul(p, l, r, m + 1, pr, d);
    sum[p] = sum[ls(p)] + sum[rs(p)];
    tot[p] = tot[ls(p)] + tot[rs(p)];
}
ll query1(int p, int l, int r, int pl, int pr)
{
    if(pl >= l && pr <= r) return sum[p];
    pushDown(p, pl, pr);
    ll res = 0;
    int m = (pl + pr) >> 1;
    if(l <= m) res += query1(ls(p), l, r, pl, m);
    if(r > m) res += query1(rs(p), l, r, m + 1, pr);
    return res;
}
ll query2(int p, int l, int r, int pl, int pr)
{
    if(pl >= l && pr <= r) return tot[p];
    pushDown(p, pl, pr);
    ll res = 0;
    int m = (pl + pr) >> 1;
    if(l <= m) res += query2(ls(p), l, r, pl, m);
    if(r > m) res += query2(rs(p), l, r, m + 1, pr);
    return res;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    while(m--)
    {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) 
        {
            printf("%lld\n", query1(1, l, r, 1, n));
        }
        else if(op == 2)
        {
            printf("%lld\n", query2(1, l, r, 1, n));
        }
        else if(op == 3)
        {
            ll x; scanf("%lld", &x);
            mul(1, l, r, 1, n, x);
        }
        else
        {
            ll x; scanf("%lld", &x);
            add(1, l, r, 1, n, x);
        }
    }
    return 0;
}