传送门

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
const int M = 370;//块数
int n, m;
ll sum[M];  //本段中的真实和是多少
ll add[M]; //本段中所有数都要加上add
int w[N];
int len;

//分块映射
int get(int x)
{
    return (x - 1) / len; //严谨写法（1 ， len）都是第一块，不然的话第一块只有len - 1个数了(1, len - 1)
}

void change(int l, int r, int d)
{
    if (get(l) == get(r)) //块内直接暴力
    {
        for (int i = l; i <= r; i ++) sum[get(i)] += d, w[i] += d;
    }
    else
    {
        //先处理两边流出的段
        int i = l, j = r;
        while (get(i) == get(l)) sum[get(i)] += d, w[i] += d, i ++;
        while (get(j) == get(r)) sum[get(j)] += d, w[j] += d, j --;
        //块间修改
        for (int k = get(i); k <= get(j); k ++) sum[k] += len * d, add[k] += d;
    }
}

ll query(int l, int r)
{
    ll ans = 0;
    if (get(l) == get(r)) //块内直接暴力
    {
        for (int i = l; i <= r; i ++) ans += w[i] + add[get(i)];
    }
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) ans += w[i] + add[get(i)], i ++;
        while (get(j) == get(r)) ans += w[j] + add[get(j)], j --;
        for (int k = get(i); k <= get(j); k ++) ans += sum[k];
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    len = sqrt(n);
    for (int i = 1; i <= n; i ++) cin >> w[i], sum[get(i)] += w[i];

    int l, r, d;
    char op;

    while (m --)
    {
        cin >> op >> l >> r;
        if (op == 'C')
        {
            cin >> d;
            change(l, r, d);
        }
        else cout << query(l, r) << "\n";
    }

    return 0;
}