P4145

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100009;
int n,q,t[N],fa[N],a,l,r;
void add(int x,int y){for(int i=x;i<=n;i+=(i&(-i))){t[i]+=y;}}
int query(int x){int ans=0;for(int i=x;i>=1;i-=(i&(-i))){ans+=t[i];}return ans;}
int get(int x){while(x!=fa[x]){x=fa[x]=fa[fa[x]];}return x;}
int merge(int x,int y){int fx=get(x),fy=get(y);if(fx!=fy){fa[fx]=fy;}}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		add(i,a),fa[i]=i;
	}
	fa[n+1]=n+1;
	cin>>q;
	while(q--){
		cin>>a>>l>>r;
		if(l>r) swap(l,r);
		if(a==0){
			for(int i=l;i<=r;){
				int now=query(i)-query(i-1),sn=sqrt(now);
				add(i,sn-now);
				if(sn==1) merge(i,i+1),i=get(i);
				else i++;
			}
		}
		if(a==1) cout<<(query(r)-query(l-1))<<endl;
	}
	return 0;
}