分析：这个题和bc round 73应该是差不多的题，当时是zimpha巨出的，那个是取phi，这个是开根
吐槽：赛场上写的时候直接维护数值相同的区间，然后1A，结果赛后糖教一组数据给hack了，仰慕
由于是开根，所以存在两个数刚开始差为1，加上某数再开根依旧是差1，这样维护相同数区间的就没用了
比如(2,3) +6-->(8,9)开根-->(2,3)如果全是这样的操作，即使维护相同的数，每次开根的复杂度都是O(N),不T才怪
这样只需要维护区间最大值最小值，当差1的时候，看看是否开根后还是差1，这样就可以变开根为减了
加强数据后，1591ms。。。（还是太年轻）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
using namespace std;
typedef long long LL;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int N=1e5+;
LL sum[N<<],lz[N<<],mx[N<<],mn[N<<];
void up(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
mx[rt]=max(mx[rt<<],mx[rt<<|]);
mn[rt]=min(mn[rt<<],mn[rt<<|]);
}
void build(int rt,int l,int r){
lz[rt]=;
if(l==r){sum[rt]=read();mn[rt]=mx[rt]=sum[rt];return;}
int mid=l+r>>;
build(rt<<,l,mid);build(rt<<|,mid+,r);
up(rt);
}
void down(int rt,int l,int r){
if(lz[rt]!=){
int mid=l+r>>;
lz[rt<<]+=lz[rt];
lz[rt<<|]+=lz[rt];
mn[rt<<]+=lz[rt];
mx[rt<<]+=lz[rt];
mx[rt<<|]+=lz[rt];
mn[rt<<|]+=lz[rt];
sum[rt<<]+=lz[rt]*(mid-l+);
sum[rt<<|]+=lz[rt]*(r-mid);
lz[rt]=;
}
}
int x,y,t,T,n,m;
void kaigen(int rt,int l,int r){
if(x<=l&&r<=y){
if(mx[rt]==mn[rt]){
lz[rt]-=mx[rt];
mx[rt]=sqrt(mx[rt]);
mn[rt]=mx[rt];
lz[rt]+=mx[rt];
sum[rt]=mx[rt]*(r-l+);
return;
}
else if(mx[rt]==mn[rt]+){
LL x1=sqrt(mx[rt]);
LL x2=sqrt(mn[rt]);
if(x1==x2+){
lz[rt]-=(mx[rt]-x1);
sum[rt]-=(mx[rt]-x1)*(r-l+);
mx[rt]=x1;mn[rt]=x2;
return;
}
}
}
int mid=l+r>>;down(rt,l,r);
if(x<=mid)kaigen(rt<<,l,mid);
if(y>mid)kaigen(rt<<|,mid+,r);
up(rt);
}
void add(int rt,int l,int r){
if(x<=l&&r<=y){
lz[rt]+=t;
sum[rt]+=1ll*(r-l+)*t;
mx[rt]+=t;mn[rt]+=t;
return ;
}
int mid=l+r>>;down(rt,l,r);
if(x<=mid)add(rt<<,l,mid);
if(y>mid)add(rt<<|,mid+,r);
up(rt);
}
LL get(int rt,int l,int r){
if(x<=l&&r<=y)return sum[rt];
int mid=l+r>>;down(rt,l,r);
LL ret=;
if(x<=mid)ret+=get(rt<<,l,mid);
if(y>mid)ret+=get(rt<<|,mid+,r);
return ret;
}
int main(){
T=read();
while(T--){
n=read();m=read();
build(,,n);
while(m--){
int op;
op=read();x=read();y=read();
if(op==){
t=read();add(,,n);
}
else if(op==)kaigen(,,n);
else printf("%I64d\n",get(,,n));
}
}
return ;
}