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