Aimee

应该用线段树的，但是用树状数组就行

反正开方这个东西只能单点修改

最后用并查集优化一下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
int n,x,y,z;
int org[1000001];
int tree[1000001];
int fa[1000001];
int q;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int lowbit(int x){
    return x&-x;
}
void add(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i)){
        tree[i]+=k;
    } 
}
int fi(int x){
    int ans=0;
    while(x){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
} 
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&org[i]);
        fa[i]=i;
        add(i,org[i]);

    }
    fa[n+1]=n+1;
    scanf("%lld",&q);
    for(int i=1;i<=q;++i){
        scanf("%lld%lld%lld",&x,&y,&z);
        if(z<y)
        swap(z,y);
        if(x==0){
            while(y<=z){
                int znx=(int)sqrt(org[y]);
                add(y,znx-org[y]);
                org[y]=znx;
                fa[y]=org[y]<=1?y+1:y;
                y=fa[y]==y?y+1:find(fa[y]) ;
            }
        } else
        cout<<fi(z)-fi(y-1)<<endl;
    }
    return 0;
}