很显然,给区间的每一个数开平方之后,他们的和不会变成原来的和的算数平方根,所以你的`change`函数是有问题的
by 半只蒟蒻 @ 2023-10-29 17:33:20
我去放错代码了
```cpp
#include<bits/stdc++.h>
#define mid (l+r)/2
#define lC q<<1
#define rC q<<1|1
#define int long long
#define INF 0x66ccff0712
#define endl "\n"
#define maxm 0x66ccff
#define maxn 0x6cf
#define void inline void
using namespace std;
inline int read(){
int s = 0,w = 1;char ch = getchar();
while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
return s*w;
}
int n,m;
int a[maxm];
struct node{
long long l,r;
long long lazy,dat;
}t[maxm];
void build(int q,int l,int r){
t[q].l=l;
t[q].r=r;
if(l==r){
t[q].dat=a[l];
return;
}
build(lC,l,mid);
build(rC,mid+1,r);
t[q].dat=t[lC].dat+t[rC].dat;
}
void change(int q,int l,int r){
if(t[q].l>r||t[q].r<l)
return;
if(t[q].l==l&&t[q].r==r){
t[q].dat=sqrt(t[q].dat);
return;
}
change(lC,l,r);
change(rC,l,r);
t[q].dat=t[lC].dat+t[rC].dat;
}
int ask(int q,int l,int r){
if(t[q].l>r || t[q].r<l)
return 0;
if(t[q].l>=l && t[q].r<=r)
return t[q].dat;
return ask(lC,l,r)+ask(rC,l,r);
}
signed main(){
int n=read(),m;
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
m=read();
for(int i=1;i<=m;i++){
int opt=read(),l=read(),r=read();
if(r<l)
swap(l,r);
if(opt==0)
for(int j=l;j<=r;j++){
if(a[j]<=1)
continue;
else
change(1,j,j);
}
else
cout<<ask(1,l,r)<<endl;
}
}
by Vsinger_洛天依 @ 2023-10-29 17:33:39
主要是T了一堆()
by Vsinger_洛天依 @ 2023-10-29 17:34:28
大概口胡一下正确的思路:
可以观察到,当一个区间的最大值小于等于 1 时,无论怎么操作这个区间都不会有变化了,所以可以考虑维护区间最大值,然后每次修改直接暴力递归,如果遇到区间最大值<=1的区间,就 return
by 半只蒟蒻 @ 2023-10-29 17:35:03
@[Vsinger_洛天依](/user/1000298) 你明明可以用线段树顺便维护区间最大值,为什么要暴力扫描
by 半只蒟蒻 @ 2023-10-29 17:35:51
@[半只蒟蒻](/user/112049) az谢谢神
by Vsinger_洛天依 @ 2023-10-29 17:36:37
您修改是 $O(n)$ 的
by Flandres @ 2023-10-29 17:37:34
@[Vsinger_洛天依](/user/1000298) $O(n)$ 修改可以拿分块卡过去捏
by Hanzelic @ 2023-10-29 17:41:59
@[Hanzelic](/user/902460) Orz我不会分块QAQ
by Vsinger_洛天依 @ 2023-10-29 17:42:34
@[Vsinger_洛天依](/user/1000298) 分块难道不比线段树好学?
by 半只蒟蒻 @ 2023-10-29 17:44:26