三种操作：区间加，区间开根号，区间求和。

修改的时候判断区间内的最大值和最小值是否相等或者差1，如果相等则变为区间赋值，否则再判断开根号之后的最大值和最小值是否相等，如果相等则区间赋值，否则区间加法。

这题的数据也忒恶心了点吧？本来直接判断相等就能解决的问题，非要加上一个玄学的优化才能过掉...

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+10,inf=0x3f3f3f3f; 5 int n,m,a[N]; 6 ll sum[N<<2],mx[N<<2],mi[N<<2],ad[N<<2],st[N<<2]; 7 #define ls (u<<1) 8 #define rs (u<<1|1) 9 #define mid ((l+r)>>1)10 void add(int u,ll x,int l,int r) {sum[u]+=x*(r-l+1),mx[u]+=x,mi[u]+=x,ad[u]+=x;}11 void Set(int u,ll x,int l,int r) {sum[u]=x*(r-l+1),mx[u]=mi[u]=x,ad[u]=0,st[u]=x;}12 void pu(int u) {sum[u]=sum[ls]+sum[rs],mx[u]=max(mx[ls],mx[rs]),mi[u]=min(mi[ls],mi[rs]);}13 void pd(int u,int l,int r) {14     if(~st[u])Set(ls,st[u],l,mid),Set(rs,st[u],mid+1,r),st[u]=-1;15     if(ad[u])add(ls,ad[u],l,mid),add(rs,ad[u],mid+1,r),ad[u]=0;16 }17 void build(int u=1,int l=1,int r=n) {18     ad[u]=0,st[u]=-1;19     if(l==r) {sum[u]=mx[u]=mi[u]=a[l]; return;}20     build(ls,l,mid),build(rs,mid+1,r),pu(u);21 }22 void upd1(int L,int R,ll x,int u=1,int l=1,int r=n) {23     if(l>=L&&r<=R) {add(u,x,l,r); return;}24     if(l>R||r
      
       =L&&r<=R&&mx[u]-mi[u]<=1) {29         if((ll)sqrt(mx[u]+0.5)==(ll)sqrt(mi[u]+0.5))Set(u,(ll)sqrt(mx[u]+0.5),l,r);30         else add(u,(ll)sqrt(mx[u]+0.5)-mx[u],l,r);31         return;32     }33     if(l>R||r
       
        =L&&r<=R)return sum[u];38     if(l>R||r