@[agosto](/user/384381) 发下代码吧,我这看不了
by calm_alone @ 2023-06-12 13:52:06
@[calm_alone](/user/811226)
```c
#include<iostream>
#include<cmath>
using namespace std;
const long long maxn = 1e5 + 5;
long long n, m, val[maxn], bl[maxn], tag[maxn], sz;
long long sum[maxn];
void Sqrt(long long a, long long b) {
for (long long i = a; i <= min(bl[a]*sz, b); i++) {
long long x = val[i];
sum[bl[a]] -= x;
val[i] = sqrt(x);
sum[bl[a]] += sqrt(x);
}
if (bl[a] != bl[b]) {
for (long long i = (bl[b] - 1) * sz + 1; i <= b; i++) {
long long x = val[i];
sum[bl[b]] -= x;
val[i] = sqrt(x);
sum[bl[b]] += sqrt(x);
}
}
for (long long i = bl[a] + 1; i <= bl[b] - 1; i++) {
if (!tag[i]) {
tag[i] = 1;
sum[i] = 0;
for (long long j = (i - 1) * sz + 1; j <= i * sz; j++) {
val[j] = sqrt(val[j]);
sum[i] += val[j];
if (val[j] > 1) {
tag[i] = 0;
}
}
}
}
}
long long query(long long a, long long b) {
long long ans = 0;
for (long long i = a; i <= min(bl[a]*sz, b); i++) {
ans += val[i];
}
if (bl[a] != bl[b]) {
for (long long i = (bl[b] - 1) * sz + 1; i <= b; i++) {
ans += val[i];
}
}
for (long long i = bl[a] + 1; i <= bl[b] - 1; i++) {
ans += sum[i];
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (long long i = 1; i <= n; i++) {
cin >> val[i];
}
sz = sqrt(n);
for (long long i = 1; i <= n; i++) {
bl[i] = (i - 1) / sz + 1;
sum[bl[i]] += val[i];
}
cin >> m;
for (long long i = 1; i <= m; i++) {
long long k, l, r, c;
cin >> k >> l >> r;
if (l > r) {
swap(l, r);
}
if (k == 0) {
Sqrt(l, r);
} else {
cout << query(l, r) << endl;
}
}
return 0;
}
```
by agosto @ 2023-06-12 13:53:10
@[agosto](/user/384381) 你那个Sqrt函数里
这块应该是把a改成i吧，因为你分块计算的时候这求的是i所在的块内的总和，你下面的循环也是这有问题。
还有最重要的一件事情
### 数组一定要保证开的够大啊！！！
你数组开小了点，下面是改了之后的代码
```cpp
#include <iostream>
#include <cmath>
using namespace std;
#define int long long
const int maxn = 5e6 + 5;
int n, m, val[maxn], pos[maxn], tag[maxn], sz;
int sum[maxn];
for (int i = pos[a] + 1; i <= pos[b] - 1; i++)
{
if (tag[i] > 0)
continue;
tag[i] = 1;
sum[i] = 0;
for (int j = (i - 1) * sz + 1; j <= i * sz; j++)
{
val[j] = sqrt(val[j]);
sum[i] += val[j];
if (val[j] > 1)
tag[i] = 0;
}
}
void Sqrt(int a, int b)
{
if (!tag[pos[a]])
{
for (int i = a; i <= min(pos[a] * sz, b); i++)
{
//int x = val[i];
sum[pos[i]] -= val[i];
val[i] = sqrt(val[i]);
sum[pos[i]] += val[i];
}
tag[pos[a]] = 1;
for (register int i = (pos[a] - 1) * sz + 1; i <= pos[a] * sz; i++)
{
if (val[i] > 1)
{
tag[pos[a]] = 0;
break;
}
}
}
if (pos[a] != pos[b] && tag[pos[b]] == 0)
{
for (int i = (pos[b] - 1) * sz + 1; i <= b; i++)
{
//int x = val[i];
sum[pos[i]] -= val[i];
val[i] = sqrt(val[i]);
sum[pos[i]] += val[i];
}
tag[pos[b]] = 1;
for (register int i = (pos[b] - 1) * sz + 1; i <= pos[b] * sz; i++)
{
if (val[i] > 1)
{
tag[pos[b]] = 0;
break;
}
}
}
}
void query(int a, int b)
{
int ans = 0;
for (int i = a; i <= min(pos[a] * sz, b); i++)
{
ans += val[i];
}
if (pos[a] != pos[b])
{
for (int i = (pos[b] - 1) * sz + 1; i <= b; i++)
{
ans += val[i];
}
}
for (int i = pos[a] + 1; i <= pos[b] - 1; i++)
{
ans += sum[i];
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> val[i];
}
sz = sqrt(n);
for (int i = 1; i <= n; i++)
{
pos[i] = (i - 1) / sz + 1;
sum[pos[i]] += val[i];
}
cin >> m;
for (int i = 1; i <= m; i++)
{
int k, l, r;
cin >> k >> l >> r;
if (l > r)
{
swap(l, r);
}
if (k == 0)
{
Sqrt(l, r);
}
else
{
//cout << query(l, r) << endl;
query(l, r);
}
}
return 0;
}
```
by calm_alone @ 2023-06-12 15:05:07
@[agosto](/user/384381) 还有，写线段树多是一件美事啊(doge
by calm_alone @ 2023-06-12 15:06:00
@[agosto](/user/384381) 好像是loj的这道题的数据有点水,而且这个块内答案进行统计的时候好像是如果像你那么写只会有那么一两个地方有细小差距，所以大概率是数据太水了
by calm_alone @ 2023-06-12 15:08:49
@[calm_alone](/user/811226)
非常感谢！！现在过了
by agosto @ 2023-06-13 13:12:47