题解：P13980 数列分块入门 5
Lonelyhacker
·
·
题解
题意
给出一个长为 n 的数列，以及 n 个操作，操作有两种（\mathrm{opt}\in\{0,1\}），涉及：
- 区间开方（\mathrm{opt}=0），令 \forall i \in [l,r],a_i \leftarrow \sqrt{a_i}。
- 区间和（\mathrm{opt}=1），求 \sum_{i=l}^{r}a_i。
## 题解
这类开方问题都有一个很典的性质。对于 $2^{31}$ 即 `INT_MAX` 而言，开 $\log_{2}31$ 次方，大约 $5\sim6$ 次就变成 $0$ 了，显然 $0$ 开方还是 $0$。善用这个性质可以让我们的代码跑得更快。我们只要记录一个块内 $1$ 的个数，在进行开方操作时遇到一个全 $0$ 的块，显然没必要继续操作，直接跳过，这样就加快了我们算法的效率。
具体而言，我们可以进行以下操作：
1. 区间开方时，对于整块，重新记录这个整块的和 `sum` 以及其块内 $1$ 的个数 `cnt`。对于散块（散点），直接暴力开根，记得将此点所在整块的 `sum` 进行修改。
2. 询问区间和是，对于散块（散点）直接暴力加，整块直接加 `sum` 即可，很方便。
## 代码
保留注释，不懂就看。
```cpp
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
int n, blo, bl[N], cnt[N];
ll v[N], sum[N]; // 现在的cnt存的是在这个整块中不为0或1的元素的个数
// INT_MAX开根6次左右就会变成1了，所以可以整块散块暴力开根，顺便更新整块cnt，当cnt==0时就可以不用开根了
void sqr(int a, int b){
for (int i = a; i <= min(bl[a]*blo, b); i++)
sum[bl[a]] -= v[i], v[i] = sqrt(v[i]), sum[bl[a]] += v[i]; // 记得sum要先减去再加上
if (bl[a] != bl[b])
for (int i = (bl[b]-1)*blo+1; i <= b; i++) sum[bl[b]] -= v[i], v[i] = sqrt(v[i]), sum[bl[b]] += v[i];
for (int i = bl[a]+1; i <= bl[b]-1; i++){
if (!cnt[i]) continue; // 说明没必要再开根了
sum[i] = 0; // 重新统计这个整块的sum
cnt[i] = 0; // 这里必须重新计数
for (int j = (i-1)*blo+1; j <= i*blo; j++){ // 前面要+1 后面不用-1
v[j] = sqrt(v[j]); // wssb写成i了
sum[i] += v[j];
if (v[j] > 1) cnt[i]++; // 更新cnt 若上面不重新计数会出现有的点被重复计算的情况
}
}
}
ll query(int a, int b){
ll res = 0; // 由于都是暴力开根，没有什么atag，直接加上v[i]即可
for (int i = a; i <= min(bl[a]*blo, b); i++) res += v[i];
if (bl[a] != bl[b]) for (int i = (bl[b]-1)*blo+1; i <= b; i++) res += v[i];
for (int i = bl[a]+1; i <= bl[b]-1; i++) res += sum[i]; // 整块就更简单了
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];
if (v[i] > 1) cnt[bl[i]]++; // 千万别忘了统计cnt!!!!!
}
for (int i = 1, f, a, b; i <= n; i++){
cin >> f >> a >> b;
if (f == 0) sqr(a, b);
else cout << query(a, b) << '\n';
}
return 0;
}
```