hdu5828，就是线段树维护区间加，区间开方，区间求和。

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long sum[400005],add[400005],ma[400005],mi[400005];
inline void pushup(long long rt)
{
	ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
	mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);	
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void pushdown(int root,int len)
{
	if(add[root])
	{	
		add[root<<1]+=add[root];
		add[root<<1|1]+=add[root];
		ma[root<<1]+=add[root];
		ma[root<<1|1]+=add[root];
		mi[root<<1]+=add[root];
		mi[root<<1|1]+=add[root];
		sum[root<<1]+=add[root]*(len-(len>>1));
		sum[root<<1|1]+=add[root]*(len>>1);
		add[root]=0;
	}
	if(ma[root<<1]==mi[root<<1])
	{
		mi[root<<1]=ma[root<<1]=mi[root<<1|1]=ma[root<<1|1]=mi[root];
		sum[root<<1]=mi[root]*(len-len>>1);
		sum[root<<1|1]=mi[root]*(len>>1);		
	}
}
void build(int l,int r,int root)
{
	if(l==r)
	{
		scanf("%lld",&sum[root]);
		ma[root]=mi[root]=sum[root];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,root<<1);
	build(mid+1,r,root<<1|1);
	pushup(root);
}
void update(long long L,long long R,long long c,long long l,long long r,long long root)
{
	if(L<=l&&r<=R)
	{
		mi[root]+=c;
		ma[root]+=c;
		add[root]+=c;
		sum[root]+=c*(r-l+1);
		return ;
	}
	pushdown(root,r-l+1);
	long long mid=(l+r)>>1;
	if(L<=mid)
		update(L,R,c,l,mid,root<<1);
	if(mid+1<=R)
		update(L,R,c,mid+1,r,root<<1|1);
	pushup(root);
}
void Sqrt(long long L,long long R,long long l,long long r,long long root)
{
	cout<<root<<" "<<l<<" "<<r<<endl;
	if(L<=l&&r<=R)
	{
		if((int)(sqrt(mi[root]))==(int)(sqrt(ma[root])))
		{
			mi[root]=ma[root]=sqrt(mi[root]);
			sum[root]=mi[root]*(r-l+1);
		}
		else if(ma[root]-mi[root]==1)
		{
			int k=ma[root]-(int)(sqrt(ma[root]));
			update(L,R,-k,1,n,root);
		}
		else
		{
			pushdown(root,r-l+1);
			int mid=(l+r)>>1;
			if(L<=mid)
				Sqrt(L,R,l,mid,root<<1);
			if(mid+1<=R)
				Sqrt(L,R,mid+1,r,root<<1|1);
			pushup(root);
		}
		return ;
	}
	pushdown(root,r-l+1);
	int mid=(l+r)>>1;
	if(L<=mid)
		Sqrt(L,R,l,mid,root<<1);
	if(mid+1<=R)
		Sqrt(L,R,mid+1,r,root<<1|1);
	pushup(root);
}
long long query(long long L,long long R,long long l,long long r,long long root)
{
	if(L<=l&&r<=R)
		return sum[root];
	pushdown(root,r-l+1);
	long long mid=(l+r)>>1;
	long long res=0;
	if(L<=mid)
		res+=query(L,R,l,mid,root<<1);
	if(mid+1<=R)
		res+=query(L,R,mid+1,r,root<<1|1);
	return res;
}
int main()
{
	cin>>n>>m;
	build(1,n,1);
	for(long long i=1;i<=m;i++)
	{
		long long op;
		cin>>op;
		if(op==1)
		{
			long long l,r,x;
			cin>>l>>r>>x;
			update(l,r,x,1,n,1);
		}
		else if(op==2)
		{
			long long l,r;
			cin>>l>>r;
			Sqrt(l,r,1,n,1);
		}
		else
		{
			long long l,r;
			cin>>l>>r;
			cout<<query(l,r,1,n,1)<<endl;
		}
	}
	return 0;
}