洛谷P4145：https://www.luogu.org/problemnew/show/P4145
思路
这道题的重点在于sqrt(1)=1 一个限制条件
与正常线段树不同的是区间修改为开方
那么我们用一个数组记录每个区间的最大值 只有当这个区间的最大值大于1时才需要开方
因此 当我们更新到叶子节点时把每个区间的最大值和sum值开方即可
注意题目中说l可能大于r 要交换
代码
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define maxn 100010
ll sum[maxn<<
2],Max[maxn<<
2],a[maxn];
ll n,m;
void build(ll l,ll r,ll k)
{
if(l==
r)
{
sum[k]=
a[l];
Max[k]=sum[k];
//叶子节点
return;
}
ll mid=(l+r)>>
1;
build(l,mid,k<<
1);
build(mid+
1,r,k<<
1|
1);
sum[k]=sum[k<<
1]+sum[k<<
1|
1];
Max[k]=max(Max[k<<
1],Max[k<<
1|
1]);
//更新上层的值
return;
}
ll query(ll x,ll y,ll l,ll r,ll k)//常规询问
{
if(x<=l&&r<=y)
return sum[k];
ll res=
0;
ll mid=(l+r)>>
1;
if(x<=mid) res+=query(x,y,l,mid,k<<
1);
if(y>mid) res+=query(x,y,mid+
1,r,k<<
1|
1);
return res;
}
void update(ll x,ll y,ll l,ll r,ll k)
{
if(l==r)
//叶子节点时
{
sum[k]=
sqrt(sum[k]);
Max[k]=
sqrt(Max[k]);
return;
}
ll mid=(l+r)>>
1;
if(x<=mid&&Max[k<<
1]>
1) update(x,y,l,mid,k<<
1);
//满足最大值大于1
if(y>mid&&Max[k<<
1|
1]>
1) update(x,y,mid+
1,r,k<<
1|
1);
sum[k]=sum[k<<
1]+sum[k<<
1|
1];
//更新上层的值
Max[k]=max(Max[k<<
1],Max[k<<
1|
1]);
}
int main()
{
cin>>
n;
for(ll i=
1;i<=n;i++) cin>>
a[i];
build(1,n,
1);
cin>>
m;
for(ll i=
1;i<=m;i++
)
{
ll k,l,r;
cin>>k>>l>>
r;
if(l>r)
//交换
{
int temp;
temp=
l;
l=
r;
r=
temp;
}
if(k==
0)
{
update(l,r,1,n,
1);
}
if(k==
1)
{
cout<<query(l,r,
1,n,
1)<<
endl;
}
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9762423.html
相关资源：JAVA上百实例源码以及开源项目
