(\)
(Description)
给出一个长度为(N)的数列，共进行(M)次操作：
-
(1 L R)：查询([L,R])区间和。
-
(2 L R)：对([L,R])内的数每个都开平方。
-
(Nin [1,10^5])，(Min [1,2 imes 10^5])，(L_i,R_iin [1,N])
(\)
(Solution)
- 发现开根操作让数字能快速变小，没几次就变成(1)了。
- 于是对下标开树状数组维护区间和，修改时用并查集跳过不用操作的点。
- 具体的写法大致是，每个数记录从当前点开始的第一个不为(1)的数的下标，每次操作完检查一下是否需要更新，若需要直接改为下一个位置，再(find)以下就找到了下一个需要操作的位置。
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100010
#define R register
#define gc getchar
using namespace std;
typedef long long ll;
ll n,m,val[N];
struct UFS{
ll f[N];
inline void reset(){for(R ll i=1;i<N;++i)f[i]=i;}
ll find(ll x){return x==f[x]?x:f[x]=find(f[x]);}
inline void merge(ll x,ll y){f[find(x)]=find(y);}
inline bool judge(ll x,ll y){return find(x)==find(y);}
}ufs;
struct BIT{
ll c[N];
inline void reset(){memset(c,0,sizeof(c));}
inline ll lowbit(ll x){return x&-x;}
inline void add(ll p,ll x){for(;p<=n;p+=lowbit(p))c[p]+=x;}
inline ll sum(ll p){ll res=0;for(;p;p-=lowbit(p))res+=c[p];return res;}
}bit;
inline ll rd(){
ll x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline void work(){
ufs.reset(); bit.reset();
for(R ll i=1;i<=n;++i) val[i]=rd(),bit.add(i,val[i]);
m=rd();
for(R ll i=1,f,l,r;i<=m;++i){
f=rd(); l=rd(); r=rd();
if(l>r)l^=r^=l^=r;
if(f==1ll) printf("%lld
",bit.sum(r)-bit.sum(l-1));
else for(R ll j=l,tmp;j<=r;){
bit.add(j,(tmp=sqrt(val[j]))-val[j]); val[j]=tmp;
if(val[j]<=1) ufs.f[j]=j+1; j=ufs.find(j)==j?j+1:ufs.f[j];
}
}
}
int main(){
int tot=0;
while(scanf("%lld",&n)!=EOF) work();
return 0;
}