数列分块入门4

题目描述

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，区间求和。

输入格式

第一行输入一个数字 $n$。

第二行输入 $n$ 个数字，第 i 个数字为 $a_i$，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $opt,l,r,c$，以空格隔开。

若 opt = 0，表示将位于 $[l,r]$ 的之间的数字都加 $c$。

若 opt = 1，表示询问位于 $[l,r]$ 的所有数字的和 $\mathrm{mod}(c+1)$。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入1：

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输出1：

1
4

数据范围

对于 $100\%$ 的数据，$1\le n\le 50000$，$-2^{31}\le others,ans\le 2^{31}-1$。

题解

与数列分块1类似，区间加法如果是散块就直接加，整块就在整块上打标记。询问时散块直接枚举，整块将预处理的整块的和加上。

块长建议开 $n^{0.66}$，这样会更快。

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[51010];
struct kuai{long long kuai_cnt, kuai_len, belong[51010], add[310], b[51010];long long kuai[310];void init(){kuai_len = sqrt(n);kuai_cnt = (n + kuai_len - 1) / kuai_len;for(int i = 1; i <= kuai_cnt; ++ i){for(int j = (i - 1) * kuai_len + 1; j <= i * kuai_len; ++ j){kuai[i] += a[j];belong[j] = i;b[j] = a[j];}}}void change(int l, int r, int d){if(belong[l] == belong[r]){for(int i = l; i <= r; ++ i){b[i] += d;}kuai[belong[l]] += (r - l + 1) * d;}else{for(int i = l; i <= belong[l] * kuai_len; ++ i){b[i] += d;kuai[belong[l]] += d;}for(int i = belong[l] + 1; i <= belong[r] - 1; ++ i){add[i] += d;kuai[i] += d * (min((long long)n, i * kuai_len) - (i - 1) * kuai_len );}for(int i = (belong[r] - 1) * kuai_len + 1; i <= r; ++ i){b[i] += d;kuai[belong[r]] += d;}}}long long query(int l, int r){if(belong[l] == belong[r]){long long ans = 0;for(int i = l; i <= r; ++ i){ans += b[i] + add[belong[l]];}return ans;}else{long long ans = 0;for(int i = l; i <= belong[l] * kuai_len; ++ i){ans += b[i] + add[belong[l]];}for(int i = belong[l] + 1; i <= belong[r] - 1; ++ i){ans += kuai[i];}for(int i = (belong[r] - 1) * kuai_len + 1; i <= r; ++ i){ans += b[i] + add[belong[r]];}return ans;}}
}k;
int main(){scanf("%d", &n);for(int i = 1; i <= n; ++ i){scanf("%d", &a[i]);}k.init();for(int i = 1; i <= n; ++ i){int op, l, r, d;scanf("%d %d %d %d", &op, &l, &r, &d);if(op == 0){k.change(l, r, d);}else{printf("%lld\n", k.query(l, r) % (d + 1));}}return 0;
}