题面：http://uoj.ac/problem/228
正解：线段树。
我们可以发现，开根号时一个区间中的数总是趋近相等。判断一个区间的数是否相等，只要判断最大值和最小值是否相等就行了。如果这个区间的数相等，那么他们开方的数也相等，我们直接转化为减去一个数就行了。
但是这是没有办法$AC$的，我们还要加一个特判，就是最大值与最小值差为$1$，且他们开方以后的差也为$1$，如$8$和$9$这两个数，这样就能通过所有数据了。复杂度证明？我不会。。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ls (x<<1)
#define rs (x<<1|1)
#define N (100010)
#define il inline
#define RG register
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; ll lazy[*N],sum[*N],mx[*N],mn[*N],a[N],n,m; il ll gi(){
RG ll x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} il void add(RG ll x,RG ll l,RG ll r,RG ll v){
sum[x]+=(r-l+)*v,mx[x]+=v,mn[x]+=v,lazy[x]+=v; return;
} il void merge(RG ll x,RG ll l,RG ll r){
sum[x]=sum[ls]+sum[rs]+(r-l+)*lazy[x];
mx[x]=max(mx[ls],mx[rs])+lazy[x];
mn[x]=min(mn[ls],mn[rs])+lazy[x];
return;
} il void build(RG ll x,RG ll l,RG ll r){
if (l==r){ sum[x]=mx[x]=mn[x]=a[l]; return; }
RG ll mid=(l+r)>>;
build(ls,l,mid),build(rs,mid+,r);
merge(x,l,r); return;
} il void update(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll v){
if (xl<=l && r<=xr){ add(x,l,r,v); return; } RG ll mid=(l+r)>>;
if (xr<=mid) update(ls,l,mid,xl,xr,v);
else if (xl>mid) update(rs,mid+,r,xl,xr,v);
else update(ls,l,mid,xl,mid,v),update(rs,mid+,r,mid+,xr,v);
merge(x,l,r); return;
} il void Sqrt(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll la){
if (xl<=l && r<=xr){
if (mn[x]==mx[x]){
RG ll del=mx[x]+la-(ll)sqrt(mx[x]+la);
add(x,l,r,-del); return;
} else{
RG ll s1=(ll)sqrt(mn[x]+la),s2=(ll)sqrt(mx[x]+la);
if (mn[x]+==mx[x] && s1+==s2){
RG ll del=mx[x]+la-s2;
add(x,l,r,-del); return;
}
}
}
RG ll mid=(l+r)>>; la+=lazy[x];
if (xr<=mid) Sqrt(ls,l,mid,xl,xr,la);
else if (xl>mid) Sqrt(rs,mid+,r,xl,xr,la);
else Sqrt(ls,l,mid,xl,mid,la),Sqrt(rs,mid+,r,mid+,xr,la);
merge(x,l,r); return;
} il ll query(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll la){
if (xl<=l && r<=xr) return sum[x]+(r-l+)*la;
RG ll mid=(l+r)>>; la+=lazy[x];
if (xr<=mid) return query(ls,l,mid,xl,xr,la);
else if (xl>mid) return query(rs,mid+,r,xl,xr,la);
else return query(ls,l,mid,xl,mid,la)+query(rs,mid+,r,mid+,xr,la);
} il void work(){
n=gi(),m=gi(); for (RG ll i=;i<=n;++i) a[i]=gi(); build(,,n);
for (RG ll i=,type,l,r,x;i<=m;++i){
type=gi();
if (type==) l=gi(),r=gi(),x=gi(),update(,,n,l,r,x);
if (type==) l=gi(),r=gi(),Sqrt(,,n,l,r,);
if (type==) l=gi(),r=gi(),printf("%lld\n",query(,,n,l,r,));
}
return;
} int main(){
File("standard");
work();
return ;
}