题解:区间开方emmm,这马上让我想起了当时写线段树的时候,很显然,对于一个在2^31次方以内的数,开方7-8次就差不多变成一了,所以我们对于每次开方,如果块中的所有数都为一了,那么开方也没有必要了.
所以开个tag标记一下当前块是否均为一,如果不是的话每次暴力构块即可
代码如下:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; long long a[],tag[],sum[],lump[];
int n,sz; void reset(int x)
{
if(tag[x])
{
return;
}
sum[x]=;
tag[x]=;
for(int i=(x-)*sz+;i<=min(sz*x,n);i++)
{
a[i]=sqrt(a[i]);
sum[x]+=a[i];
if(a[i]>)
{
tag[x]=;
}
}
} void add(long long l,long long r)
{
for(int i=l;i<=min(sz*lump[l],r);i++)
{
sum[lump[i]]-=a[i]; //lump!!!
a[i]=sqrt(a[i]);
sum[lump[i]]+=a[i];
}
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*sz+;i<=r;i++)
{
sum[lump[i]]-=a[i];
a[i]=sqrt(a[i]);
sum[lump[i]]+=a[i];
}
}
for(int i=lump[l]+;i<=lump[r]-;i++)
{
reset(i);
}
} long long query(long long l,long long r)
{
long long ans=;
for(int i=l;i<=min(lump[l]*sz,r);i++)
{
ans+=a[i];
}
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*sz+;i<=r;i++)
{
ans+=a[i];
}
}
for(int i=lump[l]+;i<=lump[r]-;i++)
{
ans+=sum[i];
}
return ans;
} int main()
{
long long opt,l,r,c;
scanf("%d",&n);
sz=sqrt(n);
for(int i=;i<=n;i++)
{
lump[i]=(i-)/sz+;
scanf("%lld",&a[i]);
}
for(int i=;i<=n;i++)
{
sum[lump[i]]+=a[i];
}
for(int i=;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);
if(!opt)
{
add(l,r);
}
else
{
printf("%lld\n",query(l,r));
}
}
}