分块维护区间开根号和区间和

自己数据与标程无差别，但loj上只有30

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5,ghN=300;
int n,a[N],belong[N],L[ghN],R[ghN],sum[ghN],flag[ghN],block,tot;
inline void init()
{
	block=sqrt(n);
	tot=(n-1)/block+1;
	for(int i=1;i<=tot;i++)
		L[i]=R[i-1]+1,R[i]=i*block;
	for(int i=1;i<=tot;i++)
		for(int j=L[i];j<=R[i];j++)
			belong[j]=i,sum[i]+=a[j];
	return;
}
inline void sqrt_solve(int x)
{
	if(flag[x])return;
	flag[x]=1;
	sum[x]=0;
	for(int i=L[x];i<=R[x];i++)
	{
		a[i]=sqrt(a[i]);
		sum[x]+=a[i];
		if(a[i]>1)flag[x]=0;
	}
	return;
}
inline void modify(int l,int r)
{
	if(belong[l]==belong[r])
	{
		int p=belong[l];
		for(int i=l;i<=r;i++)
		{
			sum[p]-=a[i];
			a[i]=sqrt(a[i]);
			sum[p]+=a[i];
		}
		return;
	}
	int p=belong[l],q=belong[r];
	for(int i=p+1;i<=q-1;i++)
		sqrt_solve(i);
	for(int i=l;i<=R[p];i++)
	{
		sum[p]-=a[i];
		a[i]=sqrt(a[i]);
		sum[p]+=a[i];
	}
	for(int i=r;i>=L[q];i--)
	{
		sum[q]-=a[i];
		a[i]=sqrt(a[i]);
		sum[q]+=a[i];
	}
	return;
}
inline int query(int l,int r)
{
	int ans=0;
	if(belong[l]==belong[r])
	{
		for(int i=l;i<=r;i++)
			ans+=a[i];
		return ans;
	}
	int p=belong[l],q=belong[r];
	for(int i=p+1;i<=q-1;i++)
		ans+=sum[i];
	for(int i=l;i<=R[p];i++)
		ans+=a[i];
	for(int i=r;i>=L[q];i--)
		ans+=a[i];
	return ans;
}
signed main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();
	while(n--)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0)
			modify(l,r);
		else
			cout<<query(l,r)<<endl;
	}
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}