题解：P13982 数列分块入门 7
Lonelyhacker
·
·
题解
题意
给出一个长为 n 的数列，以及 n 个操作，操作有三种（\mathrm{opt}\in\{0,1,2\}），涉及：
- 区间加（\mathrm{opt}=0），令 \forall i \in [l,r],a_i \leftarrow a_i+c。
- 区间乘（\mathrm{opt}=1），令 \forall i \in [l,r],a_i \leftarrow a_i\cdot c。
- 单点查（\mathrm{opt}=2），求 a_r 对 10007 取模后的非负的结果。
## 题解
什么？区间加区间乘，还只求单点值？易验丁真，鉴定为：[【模板】线段树 2](https://www.luogu.com.cn/problem/P3373) 弱化版，显然将代码直接 copy 过来就能轻松 A 掉，理论复杂度还更优秀。
但这是数列分块题，所以还是讲讲分块做法。[数列分块入门 4](https://www.luogu.com.cn/problem/P13979) 的要求是区间加区间和，此题多了个区间乘，区间和改成了单点查，可在原来基础上进行升级（降级）。具体地，直接再开一个数组 `mul` 存乘法的懒标记，由于不用区间和，可以不开存储每个块内的值之和的数组（我之前开的 `sum`）。思路和线段树 $2$ 的差不多，都是先乘后加，好维护。区间加就直接暴力 or 懒标记，区间乘就记得给加法懒标记也乘上，单点查询就将原值乘上其所在块的乘法懒标记再加上其所在块的假发懒标记。
注意一个细节：对于散块（散点）的暴力修改，必须将其所在块的懒标记先下传，不能直接在原值上进行修改，否则日后求这个单点的值是错的。
记得取模。记得保证结果非负。
## 代码
虽然到处乱取模很慢，但是没办法，不然就溢出了。
```cpp
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 3e5+5, mod = 1e4+7;
int n, blo, bl[N];
ll v[N], add[N], mul[N];
// 此题与线段树2大同小异，我的写法原则仍为先乘后加
// 整块维护简单，加法时正常加，乘法时就给add和mul都乘
// 散块维护前必须先将其所在整块的标记下发，也就是下面push_down的作用
void push_down(int x){
for (int i = (x-1)*blo+1; i <= min(x*blo, n); i++)
v[i] = (mul[x]*v[i]%mod+add[x])%mod;
add[x] = 0;
mul[x] = 1; // 谨记
}
void add_(int a, int b, ll c){
push_down(bl[a]);
for (int i = a; i <= min(bl[a]*blo, b); i++) v[i] = (v[i]+c)%mod;
if (bl[a] != bl[b]){
push_down(bl[b]);
for (int i = (bl[b]-1)*blo+1; i <= b; i++) v[i] = (v[i]+c)%mod;
}
for (int i = bl[a]+1; i <= bl[b]-1; i++) add[i] = (add[i]+c)%mod;
}
void mul_(int a, int b, ll c){
push_down(bl[a]);
for (int i = a; i <= min(bl[a]*blo, b); i++) v[i] = (v[i]*c)%mod;
if (bl[a] != bl[b]){
push_down(bl[b]);
for (int i = (bl[b]-1)*blo+1; i <= b; i++) v[i] = (v[i]*c)%mod;
}
for (int i = bl[a]+1; i <= bl[b]-1; i++) add[i] = (add[i]*c)%mod, mul[i] = (mul[i]*c)%mod;
}
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;
mul[bl[i]] = 1; // 谨记 初始化
}
for (int i = 1, f, a, b, c; i <= n; i++){
cin >> f >> a >> b >> c;
if (f == 0) add_(a, b, c);
else if (f == 1) mul_(a, b, c);
else cout << ((v[b]*mul[bl[b]]%mod+add[bl[b]])%mod+mod)%mod << '\n';
}
return 0;
}
```
## 后日谈
记得上面说的理论复杂度更优秀吗？还真是更优秀。
[线段树最快记录](https://www.luogu.com.cn/record/234855268) vs [分块最快记录](https://www.luogu.com.cn/record/234859873)，快了近一倍。
当然这种问题肯定写线段树会更好一些了。