@[BugGod](/user/541254) 早年代码,马蜂清奇,不喜勿喷。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node
{
int l,r,max,sum;
}t[N<<2];
int n,m,a[N];
void use4(int p)
{
t[p].sum=t[2*p].sum+t[2*p+1].sum;
t[p].max=max(t[2*p].max,t[2*p+1].max);
}
inline void use0(int left,int right,int index)
{
t[index].l=left;
t[index].r=right;
if(left==right)
{
t[index].sum=a[left];
t[index].max=a[left];
return ;
}
int mid=(right+left)/2;
use0(left,mid,index*2);
use0(mid+1,right,index*2+1);
use4(index);
}
void use1(int p,int L,int R)
{
if(t[p].max==1)
{
return;
}
if(t[p].l==t[p].r)
{
t[p].sum=sqrt(t[p].sum);
t[p].max=t[p].sum;
return;
}
int mid=t[p].l+t[p].r>>1;
if(L<=mid)
{
use1(2*p,L,R);
}
if(mid<R)
{
use1(2*p+1,L,R);
}
use4(p);
}
int use2(int p,int L,int R)
{
if(L<=t[p].l&&t[p].r<=R)
{
return t[p].sum;
}
int ret=0;
int mid=t[p].l+t[p].r>>1;
if(L<=mid)
{
ret+=use2(2*p,L,R);
}
if(mid<R)
{
ret+=use2(2*p+1,L,R);
}
return ret;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
use0(1,n,1);
while(m--)
{
int k,l,r;
cin>>k>>l>>r;
if(l>r)
{
swap(l,r);
}
if(k==0)
{
use1(1,l,r);
}
else
{
cout<<use2(1,l,r)<<endl;
}
}
return 0;
}
```
by lovely_hyzhuo @ 2024-02-06 11:28:57
奇怪,为什么感觉都一样,但是样例寄了。
by BugGod @ 2024-02-06 11:37:42
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(x) x<<1
#define rs(x) x<<1|1
#define val(x) tree[x].val
#define maxx(x) tree[x].maxx
int n,m,a[100010];
struct xds
{
struct Tree
{
int val,maxx;
}tree[400010];
void pushup(int p)
{
val(p)=val(ls(p))+val(rs(p));
maxx(p)=max(maxx(ls(p)),maxx(rs(p)));
}
void build(int p,int l,int r)
{
if(l==r)
{
val(p)=maxx(p)=a[l];
return ;
}
int mid=l+r>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
void add(int p,int l,int r,int L,int R)
{
if(l==r)
{
val(p)=sqrt(val(p));
maxx(p)=sqrt(maxx(p));
return ;
}
int mid=l+r>>1;
if(mid>=L&&maxx(ls(p))>1)add(ls(p),l,mid,L,R);
if(mid<R&&maxx(rs(p))>1)add(rs(p),mid+1,r,L,R);
pushup(p);
}
int query(int p,int l,int r,int L,int R)
{
if(R<l||L>r)return 0;
if(L<=l&&r<=R)return val(p);
int mid=l+r>>1,ans=0;
if(mid>=L)ans+=query(ls(p),l,mid,L,R);
if(mid<r)ans+=query(rs(p),mid+1,r,L,R);
return ans;
}
}tr;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
tr.build(1,1,n);
for(int i=1;i<=m;i++)
{
int opt,l,r;
cin>>opt>>l>>r;
if(l>r)swap(l,r);
if(opt==0)tr.add(1,1,n,l,r);
if(opt==1) cout<<tr.query(1,1,n,l,r)<<endl;
}
return 0;
}
```
线段树建树,`val(p)=maxx(p)=a[l]` 而不是 `val(p)=maxx(p)=a[p]`
by Fiendish @ 2024-02-06 11:48:14
@[BugGod](/user/541254)
by Fiendish @ 2024-02-06 11:48:28
@[Fiendish](/user/688892) 草,thx。
by BugGod @ 2024-02-06 11:50:35