题意：

sol  ：线段树开根操作

　　　对于节点x，可以在max[x]-min[x]<=1时直接做，转化为区间减或区间覆盖

#include
     
      #include
      
       #include
       
        #include
        
         #define int long longusing namespace std;const int Mx=800010;int n,m,a[Mx],Min[Mx],Max[Mx],sum[Mx];int l[Mx],r[Mx],lson[Mx],rson[Mx],Add_tag[Mx],Cover_tag[Mx];void pushup(int x){    int L=lson[x],R=rson[x];    Min[x]=min(Min[L],Min[R]);    Max[x]=max(Max[L],Max[R]);    sum[x]=sum[L]+sum[R];}void build(int x,int L,int R){    l[x]=L,r[x]=R,lson[x]=x<<1,rson[x]=x<<1|1;    if(L==R) { Min[x]=a[L],Max[x]=a[L],sum[x]=a[L]; return ;}    int mid=(L+R)>>1;    build(x<<1,L,mid);    build(x<<1|1,mid+1,R);    pushup(x);}void pushdown(int x){    int LS=lson[x],RS=rson[x],LL=l[LS],LR=r[LS],RL=l[RS],RR=r[RS];    if(Add_tag[x]!=0)    {        Max[LS]+=Add_tag[x],Min[LS]+=Add_tag[x],sum[LS]+=(LR-LL+1)*Add_tag[x];        Max[RS]+=Add_tag[x],Min[RS]+=Add_tag[x],sum[RS]+=(RR-RL+1)*Add_tag[x];        if(Cover_tag[LS]<1e8) Cover_tag[LS]+=Add_tag[x];        else Add_tag[LS]+=Add_tag[x];        if(Cover_tag[RS]<1e8) Cover_tag[RS]+=Add_tag[x];        else Add_tag[RS]+=Add_tag[x];    }    if(Cover_tag[x]<1e8)    {        Max[LS]=Cover_tag[x],Min[LS]=Cover_tag[x],sum[LS]=(LR-LL+1)*Cover_tag[x];        Max[RS]=Cover_tag[x],Min[RS]=Cover_tag[x],sum[RS]=(RR-RL+1)*Cover_tag[x];        Cover_tag[LS]=Cover_tag[x];        Cover_tag[RS]=Cover_tag[x];    }    Add_tag[x]=0,Cover_tag[x]=1e9;}void Add(int x,int ql,int qr,int val){    int L=l[x],R=r[x];    if(ql>R||qr
         
          =R)    {        if(Cover_tag[x]<1e8) Cover_tag[x]+=val;        else Add_tag[x]+=val;        Max[x]+=val,Min[x]+=val,sum[x]+=(R-L+1)*val;        return ;    }    pushdown(x);    Add(lson[x],ql,qr,val);    Add(rson[x],ql,qr,val);    pushup(x);}void Cover(int x,int ql,int qr,int val){    int L=l[x],R=r[x];    Add_tag[x]=0,Cover_tag[x]=val;    Max[x]=val,Min[x]=val,sum[x]=(R-L+1)*val;}void Sqrt(int x,int ql,int qr){    int L=l[x],R=r[x];    if(ql>R||qr
          
           =R&&Max[x]-Min[x]<=1) { int mx=(int)sqrt(Max[x]),mn=(int)sqrt(Min[x]); if(mx==mn) Cover(x,L,R,mx); else Add(x,L,R,mx-Max[x]); return ; } pushdown(x); Sqrt(lson[x],ql,qr); Sqrt(rson[x],ql,qr); pushup(x);}int Query(int x,int ql,int qr){ int L=l[x],R=r[x]; if(ql>R||qr
           
            =R) return sum[x]; pushdown(x); int ans=Query(lson[x],ql,qr)+Query(rson[x],ql,qr); pushup(x); return ans;}signed main(){ for(int i=0;i