题面

题解

区间求和\(+\)区间修改板子，这里用分块写的

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using std::min; using std::max;using std::swap; using std::sort;typedef long long ll;#define int llconst int N = 1e5 + 10 , SN = 340;int n, siz, q, bel[N], val[N];int sum[SN], add[SN], L[SN], R[SN];template
        
         void read(T &x) {    int flag = 1; x = 0; char ch = getchar();    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;}void modify (int l, int r, int c) {    int fl = bel[l], fr = bel[r];    if(fl == fr) {        for(int i = l; i <= r; ++i)            val[i] += c, sum[fl] += c;    } else {        for(int i = l; i <= R[fl]; ++i)            val[i] += c, sum[fl] += c;        for(int i = fl + 1; i < fr; ++i) add[i] += c;        for(int i = L[fr]; i <= r; ++i)            val[i] += c, sum[fr] += c;    }}int query(int l, int r) {    int fl = bel[l], fr = bel[r], ret = 0;    if(fl == fr) {        for(int i = l; i <= r; ++i)            ret += val[i] + add[fl];    } else {        for(int i = l; i <= R[fl]; ++i)            ret += val[i] + add[fl];        for(int i = fl + 1; i < fr; ++i) ret += sum[i] + add[i] * (R[i] - L[i] + 1);        for(int i = L[fr]; i <= r; ++i)            ret += val[i] + add[fr];    } return ret;}signed main () {    read(n), read(q), siz = sqrt(n);    for(int i = 1; i <= n; ++i)        read(val[i]), bel[i] = (i - 1) / siz + 1, sum[bel[i]] += val[i];    for(int i = 1; i <= bel[n]; ++i)        L[i] = R[i - 1] + 1, R[i] = i * siz;    R[bel[n]] = n; int l, r, k;    while(q--) {        char opt; scanf("\n%c", &opt);        read(l), read(r);        if(opt == 'Q') printf("%lld\n", query(l, r));        else read(k), modify(l, r, k);    }    return 0;}