第二行输入 个数字，第 个数字为 ，以空格隔开。
有 行询问，每行输入三个数字 ，以空格隔开。
若 ，表示将位于 的之间的数字都开方。对于区间中每个
若 ，表示询问位于 的所有数字的和。
区间开方，发现不能打懒标记。
打我们发现一个性质：一个大数，开 次方，最后也会变成 或 。
所以，开方暴力遍历即可。若该块内元素均已变为 或 ，就跳过这个块。
注意同时维护每个块的和。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+7;
int a[N],b[N],id[N],n,len,s[N];
bool flg[N];
void upd(int j){
s[id[j]]-=a[j];
a[j]=(int)sqrt(a[j]);
s[id[j]]+=a[j];
}
bool check(int bid){
bool f=1;
int lf=(bid-1)*len+1,ri=min(n,bid*len);
for(int i=lf;i<=ri;i++)if(a[i]>1)f=0;
return f;
}
void sqrted(int l,int r){
if(id[l]==id[r]){
if(flg[id[l]])return;
for(int i=l;i<=r;i++)upd(i);
flg[id[l]]=check(id[l]);
return;
}
if(!flg[id[l]]){
for(int i=l;id[i]==id[l];i++)upd(i);
flg[id[l]]=check(id[l]);
}
for(int i=id[l]+1;i<id[r];i++){
if(!flg[i]){
int lf=(i-1)*len+1,ri=min(n,len*i);
for(int j=lf;j<=ri;j++)upd(j);
flg[i]=check(i);
}
}
if(!flg[id[r]]){
for(int i=r;id[i]==id[r];i--)upd(i);
flg[id[r]]=check(id[r]);
}
}
int query(int l,int r){
int ans=0;
if(id[l]==id[r]){
for(int i=l;i<=r;i++)ans+=a[i]+b[id[l]];
return ans;
}
for(int i=l;id[i]==id[l];i++)ans+=a[i]+b[id[l]];
for(int i=id[l]+1;i<id[r];i++)ans+=s[i];
for(int i=r;id[i]==id[r];i--)ans+=a[i]+b[id[r]];
return ans;
}
signed main(){
cin>>n;
len=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
id[i]=(i-1)/len+1;
s[id[i]]+=a[i];
}
for(int i=1;i<=n;i++){
int opt,l,r,c;
cin>>opt>>l>>r;
if(opt==0)sqrted(l,r);
else print("{}\n",query(l,r));
}
}
暂无评论