参考：https://www.cnblogs.com/ljh2000-jump/p/6357583.html
考虑当整个区间的最大值开方==最小值开方（实质上就是区间开完方后所有数都相等），那么我们开一次方就可以了。
听说有证明如果达到上面的那种情况的话最多需要操作O(lg^2)次，那么复杂度就是O(n*lg^3)了。
实际上开方只是起到了一个缩小最大值和最小值差值的作用，当差值缩小为0时就是我们所想要的那种情况。
但是也有极端数据比如898989，开完方变成343434……无限下去你就会发现无论怎么开所有的数都会差1，复杂度瞬间被艹。
对于这种极端数据实际上只是进行了一次区间减，我们特判之就能保证复杂度了。
另外为了减少代码编写难度，采用了参考的那种只有当最大值==最小值才开方的写法，虽然最好情况下复杂度会增加，但是最坏情况复杂度并没有增加，所以没有问题。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+;
inline ll read(){
ll X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
int n,m;
ll b[N],sum[N*],ad[N*],maxn[N*],minn[N*];
inline void mdy(int a,int l,int r,ll w){
sum[a]+=w*(r-l+);
maxn[a]+=w;minn[a]+=w;
ad[a]+=w;
}
inline void upt(int a,int l,int r){
int ls=a<<,rs=a<<|;
sum[a]=sum[ls]+sum[rs]+ad[a]*(r-l+);
maxn[a]=max(maxn[ls],maxn[rs])+ad[a];
minn[a]=min(minn[ls],minn[rs])+ad[a];
}
void build(int a,int l,int r){
if(l==r){
sum[a]=maxn[a]=minn[a]=b[l];
return;
}
int mid=(l+r)>>;
build(a<<,l,mid);build(a<<|,mid+,r);
upt(a,l,r);
}
void seg_add(int a,int l,int r,int l1,int r1,ll w){
if(r<l1||r1<l)return;
if(l1<=l&&r<=r1){
mdy(a,l,r,w);
return;
}
int mid=(l+r)>>;
seg_add(a<<,l,mid,l1,r1,w);seg_add(a<<|,mid+,r,l1,r1,w);
upt(a,l,r);
}
void seg_sqrt(int a,int l,int r,int l1,int r1,ll w){
if(r<l1||r1<l)return;
if(l1<=l&&r<=r1){
ll delta,c1=sqrt(minn[a]+w),c2=sqrt(maxn[a]+w);
if(maxn[a]==minn[a]){
delta=minn[a]+w-(ll)sqrt(minn[a]+w);
mdy(a,l,r,-delta);
return;
}else if(minn[a]+==maxn[a]&&c1+==c2){
delta=minn[a]+w-(ll)sqrt(minn[a]+w);
mdy(a,l,r,-delta);
return;
}
}
int mid=(l+r)>>;w+=ad[a];
seg_sqrt(a<<,l,mid,l1,r1,w);seg_sqrt(a<<|,mid+,r,l1,r1,w);
upt(a,l,r);
}
ll query(int a,int l,int r,int l1,int r1,ll w){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return sum[a]+w*(r-l+);
int mid=(l+r)>>;w+=ad[a];
return query(a<<,l,mid,l1,r1,w)+query(a<<|,mid+,r,l1,r1,w);
}
int main(){
n=read(),m=read();
for(int i=;i<=n;i++)b[i]=read();
build(,,n);
while(m--){
int op=read(),x=read(),y=read();
if(op==)seg_add(,,n,x,y,read());
if(op==)seg_sqrt(,,n,x,y,);
if(op==)printf("%lld\n",query(,,n,x,y,));
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++