嗯...
题目链接：https://loj.ac/problem/6277
这里是数列分块的基本操作：区间加和单点查询。
数列分块其实就是一个带优化的枚举。
首先将n个数分成sqrt(n)个块，然后记录块的大小、个数、左右端点等。
当在区间修改时分成三部分。 add数组应该是优化的关键。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 5 using namespace std; 6 7 const int maxn = 510; 8 const int N = 100010; 9 10 int block, num; 11 int L[maxn], R[maxn], add[maxn]; 12 int belong[N], a[N]; 13 14 inline void build(int n){ 15 block = sqrt(n); 16 num = ceil(n * 1.0 / block); 17 for(int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1; 18 for(int i = 1; i <= num; i++){ 19 L[i] = (i - 1) * block + 1; 20 R[i] = i * block; 21 } 22 R[num] = n; 23 } 24 25 inline void modify(int l, int r, int c){ 26 for(int i = l; i <= min(r, R[belong[l]]); i++) a[i] += c; 27 if(belong[l] != belong[r]) 28 for(int i = L[belong[r]]; i <= r; i++) a[i] += c; 29 for(int i = belong[l] + 1; i < belong[r]; i++) add[i] += c; 30 } 31 32 int main(){ 33 int n; 34 scanf("%d", &n); 35 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 36 build(n); 37 for(int i = 1; i <= n; i++){ 38 int opt, l, r, c; 39 scanf("%d%d%d%d", &opt, &l, &r, &c); 40 if(opt == 1) printf("%d\n", a[r] + add[belong[r]]); 41 else modify(l, r, c); 42 } 43 return 0; 44 }