Poj3468 A Simple Problem with Integers （分块）

题面

Poj

题解

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

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;
#define int ll

const int N = 1e5 + 10 , SN = 340;
int n, siz, q, bel[N], val[N];
int sum[SN], add[SN], L[SN], R[SN];

template<typename T>
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;
}