1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <cstdio> using namespace std; typedef long long LL; const int N = 100001; int n, q, l, r, c, a[N << 2]; char ch; LL d[N << 2], b[N << 2]; void build(int p, int s, int t) { if (s == t) { d[p] = a[s]; return; } int m = s + t >> 1; build(p * 2, s, m), build(p * 2 + 1, m + 1, t); d[p] = d[p * 2] + d[p * 2 + 1]; } void update(int p, LL c, int l, int r, int s, int t) { if (l <= s && t <= r) { d[p] += (t - s + 1) * c, b[p] += c; return; } int m = t + s >> 1; if (b[p] && s != t) { d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p], b[p * 2 + 1] += b[p]; b[p] = 0; } if (l <= m) update(p * 2, c, l, r, s, m); if (r > m) update(p * 2 + 1, c, l, r, m + 1, t); d[p] = d[p * 2] + d[p * 2 + 1]; } LL getSum(int p, int l, int r, int s, int t) { if (l <= s && t <= r) return d[p]; int m = s + t >> 1; if (b[p]) { d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p], b[p * 2 + 1] += b[p]; b[p] = 0; } LL sum = 0; if (l <= m) sum = getSum(p * 2, l, r, s, m); if (r > m) sum += getSum(p * 2 + 1, l, r, m + 1, t); return sum; } int main() { scanf("%d %d", &n, &q); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); build(1, 1, n); for (int i = 0; i < q; ++i) { getchar(); scanf("%c %d %d", &ch, &l, &r); if (ch == 'Q') { printf("%lld\n", getSum(1, l, r, 1, n)); } else { scanf("%d", &c); update(1, c, l, r, 1, n); } } return 0; }
|