提交记录

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1E6;
int n,t,a[N],pos[N],ll[N],rr[N],sum[N],f1[N];

inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') f=-1;
		x=x*10+ch-'0';
	}
	while(ch<='9'&&ch>='0') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

inline void change(int l,int r) {
	int p=pos[l],q=pos[r];
	if(p==q) {
		if(f1[q]==1) return;
		for(int i=l;i<=r;i++) sum[p]-=a[i], a[i]=sqrt(a[i]), sum[p]+=a[i];
		if(sum[q]==rr[q]-ll[q]+1) f1[q]=1;
	}
	else {
		if(f1[p]!=1)for(int i=l;i<=rr[p];i++) sum[p]-=a[i], a[i]=sqrt(a[i]), sum[p]+=a[i];
		if(f1[q]!=1)for(int i=ll[q];i<=r;i++) sum[q]-=a[i], a[i]=sqrt(a[i]), sum[q]+=a[i];
		if(sum[p]==rr[p]-ll[p]+1) f1[p]=1;
		if(sum[q]==rr[q]-ll[q]+1) f1[q]=1;
		for(int i=p+1;i<q;i++) {
		 	if(f1[i]==1) continue;
			for(int j=ll[i];j<=rr[i];j++) 
			 	sum[i]-=a[j], a[j]=sqrt(a[j]), sum[i]+=a[j];
			if(sum[i]==rr[i]-ll[i]+1)	f1[i]=1;
		}
	}
}

inline int ask(int l,int r) {
	int p=pos[l],q=pos[r],s=0;
	if(p==q) {
		for(int i=l;i<=r;i++) s+=a[i];
		return s;
	}
	else {
		for(int i=l;i<=rr[p];i++) s+=a[i];
		for(int i=ll[q];i<=r;i++) s+=a[i];
		for(int i=p+1;i<q;i++)  s+=sum[i];
		return s;
	}
}

signed main() {
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	t=sqrt(n);
	for(int i=1;i<=t;i++) ll[i]=(i-1)*t+1, rr[i]=i*t;
	if(rr[t]<n) ++t, ll[t]=rr[t-1]+1, rr[t]=n;
	for(int i=1;i<=t;i++) {
		for(int j=ll[i];j<=rr[i];j++) pos[j]=i, sum[i]+=a[j];
	}
	int T=read();
	while(T--) {
		int op=read(),l=read(),r=read();
		if(l>r) swap(l,r);
		if(op==0) change(l,r);
		else cout<<ask(l,r)<<endl;
	}
	return 0;
}