P4145 上帝造题的七分钟 2 / 花神游历各国
代码如下：

#include<bits/stdc++.h>
#define MAXN 1000009
#define ll long long
using namespace std;
ll n,m,op,x,y;
ll block[MAXN],l[2450],r[2450];
ll a[MAXN],sumx[2450],maxx[2450];
void init(){
	ll bs=sqrt(n),mb=(n-1)/bs+1;
	for(int i=1;i<=n;i++){
		block[i]=(i-1)/bs+1;
		sumx[block[i]]+=a[i];
		maxx[block[i]]=max(maxx[block[i]],a[i]);
	} 
	for(int i=1;i<=mb;i++){
		l[i]=(i-1)*bs+1;
		r[i]=i*bs;
	}
	r[mb]=n;
}
void modify(int L,int R){
	int bl=block[L],br=block[R];
	if(bl==br){
		if(maxx[bl]<=1) return ;
		for(int i=L;i<=R;i++){
			sumx[bl]=sumx[bl]-a[i]+sqrt(a[i]);
			a[i]=sqrt(a[i]);
		} 
		for(int i=l[bl];i<=r[bl];i++) maxx[bl]=max(maxx[bl],a[i]);
	} 
	else{
		if(maxx[bl]>1){
			for(int i=L;i<=r[bl];i++){
				sumx[bl]=sumx[bl]-a[i]+sqrt(a[i]);
				a[i]=sqrt(a[i]);	
			}
			for(int i=l[bl];i<=r[bl];i++) maxx[bl]=max(maxx[bl],a[i]);
		}
		for(int i=bl+1;i<=br-1;i++){
			if(maxx[i]<=1) continue;
			for(int j=l[i];j<=r[i];j++){
				sumx[i]=sumx[i]-a[j]+sqrt(a[j]);
				a[j]=sqrt(a[j]);	
			}
			maxx[i]=sqrt(maxx[i]);
		}
		if(maxx[br]>1){
			for(int i=l[br];i<=R;i++){
				sumx[br]=sumx[br]-a[i]+sqrt(a[i]);
				a[i]=sqrt(a[i]);
			} 
			for(int i=l[br];i<=r[br];i++) maxx[br]=max(maxx[br],a[i]);
		}
	}
}
ll query(int L,int R){
	int bl=block[L],br=block[R];
	ll ans=0;
	if(bl==br){
		for(int i=L;i<=R;i++) ans+=a[i];
	}
	else{
		for(int i=L;i<=r[bl];i++) ans+=a[i];
		for(int i=bl+1;i<=br-1;i++) ans+=sumx[i];
		for(int i=l[br];i<=R;i++) ans+=a[i];
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	init();
	cin>>m;
	while(m--){
		cin>>op>>x>>y;
		if(x>y) swap(x,y);
		if(op) cout<<query(x,y)<<endl;
		else modify(x,y);
	}
	return 0;
}