题解：P13979 数列分块入门 4
Lonelyhacker
·
·
题解
题意
给出一个长为 n 的数列，以及 n 个操作，操作有两种（\mathrm{opt}\in\{0,1\}），涉及：
- 区间加（\mathrm{opt}=0），令 \forall i \in [l,r],a_i \leftarrow a_i+c。
- 区间和（\mathrm{opt}=1），求 \sum_{i=l}^r a_i 对 (c+1) 取模后的结果。
## 题解
什么？区间加区间和？已验丁真，鉴定为：[【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)。因此，直接将线段树 $1$ 的代码粘贴过来这题就做完了，理论复杂度还更优秀。
当然我们还是要讲讲分块做法的。[数列分块入门 1](https://www.luogu.com.cn/problem/P13976) 的要求是区间加单点查，此题为区间查，可在原来基础上进行升级。具体地，我们开一个 `sum` 数组存储每个块的值的总和，查询时对于散块（散点），直接暴力加上其值及其所在块的懒标记；对于整块，直接加上 `sum`，但是懒标记也要下传。设块长为 `blo`，懒标记为 `tag`，则其贡献为 `tag*blo`。
记得取模。记得确保结果非负。
## 代码
给被卡常的小朋友们一点建议：取模是很慢的，瞎取模直接就 T 飞了，在那些数论题更为明显。注意到 $2^{31}$ 约等于 $2\times10^9$，而 $n \le 3\times10^5$，因此最大值仅为 $6\times10^{14}$，`long long` 存得下，因此在最后结果取模即可。
如果你还是被卡了，加快读，`inline`，数组加 `static`，改块长这些都可以试试。如果还是不行有可能是你的实现太差了，学习一下别人的代码罢。
```cpp
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
int n, blo, bl[N];
ll v[N], atag[N], sum[N]; // 十年OI
void add(int a, int b, ll c){
for (int i = a; i <= min(bl[a]*blo, b); i++)
v[i] += c, sum[bl[a]] += c; // 散块加上了，其所在整块的sum也要加上c
if (bl[a] != bl[b])
for (int i = (bl[b]-1)*blo+1; i <= b; i++) v[i] += c, sum[bl[b]] += c; // 同理
for (int i = bl[a]+1; i <= bl[b]-1; i++) atag[i] += c; // 整块的话直接放在atag即可
}
int query(int a, int b, ll c){
ll res = 0;
for (int i = a; i <= min(bl[a]*blo, b); i++)
res += v[i]+atag[bl[a]]; // 散块的处理方法
if (bl[a] != bl[b])
for (int i = (bl[b]-1)*blo+1; i <= b; i++)
res += v[i]+atag[bl[b]]; // 同上
for (int i = bl[a]+1; i <= bl[b]-1; i++) res += sum[i]+atag[i]*blo; // 整块不仅要加sum，还要下发atag，两个一起加
res %= c; if (res < 0) res += c;
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
blo = sqrt(n);
for (int i = 1; i <= n; i++){
cin >> v[i];
bl[i] = (i-1)/blo+1;
sum[bl[i]] += v[i];
}
for (int i = 1, f, a, b, c; i <= n; i++){
cin >> f >> a >> b >> c;
if (f == 0) add(a, b, c);
else cout << query(a, b, c+1) << '\n';
}
return 0;
}
```
## 后日谈
记得上面说的理论复杂度更优秀吗？但线段树的常数还是太大了，我自己写的应该算复杂度比较优秀的了，但居然跑不过分块。
[线段树最快纪录](https://www.luogu.com.cn/record/234661382) vs [分块最快纪录](https://www.luogu.com.cn/record/234661779)，双方选手均未加快读，`inline` 等优化。