https://www.acwing.com/problem/content/244/
分块入门练习题
大块维护,小块朴素
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n, m, t;
int L[maxn], R[maxn], pos[maxn];
ll a[maxn], add[maxn], sum[maxn];
char s[10];
void modify(int l, int r, ll d){
int p = pos[l], q = pos[r];
if(p == q){
for(int i = l; i <= r; ++i) a[i] += d;
sum[p] += 1ll * (r - l + 1) * d;
} else{
for(int i = p + 1; i <= q - 1; ++i) add[i] += d;
for(int i = l; i <= R[p]; ++i) a[i] += d;
sum[p] += 1ll * d * (R[p] - l + 1);
for(int i = L[q]; i <= r; ++i) a[i] += d;
sum[q] += 1ll * d * (r - L[q] + 1);
}
}
ll query(int l, int r){
ll res = 0;
int p = pos[l], q = pos[r];
if(p == q){
for(int i = l; i <= r; ++i) res += a[i];
res += 1ll * (r - l + 1) * add[p];
} else{
for(int i = p + 1; i <= q - 1; ++i) res += sum[i] + 1ll * add[i] * (R[i] - L[i] + 1);
for(int i = l ; i <= R[p] ; ++i) res += a[i];
res += 1ll * add[p] * (R[p] - l + 1);
for(int i = L[q] ; i <= r ; ++i) res += a[i];
res += 1ll * add[q] * (r - L[q] + 1);
}
return res;
}
ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]);
// 分块
t = sqrt(n);
for(int i = 1; i <= t; ++i){
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
if(R[t] < n){
++t; L[t] = R[t - 1] + 1; R[t] = n;
}
// 预处理
for(int i = 1; i <= t; ++i){
for(int j = L[i]; j <= R[i]; ++j){
pos[j] = i;
sum[i] += a[j];
}
}
int l, r, d;
for(int i = 1; i <= m; ++i){
scanf("%s%d%d", s, &l, &r);
if(s[0] == 'C'){
scanf("%lld", &d);
modify(l, r, d);
} else{
printf("%lld\n", query(l, r));
}
}
return 0;
}