本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-23 13:27:51

类似区间取模，我们发现即使极差极大的序列，在经过几次开方之后便可以趋近于相等，最后序列中的元素都变成 $1$。

我们不难发现，当序列中的数都相等时，将序列开方，发现序列里的数均相同。换句话说，将序列开方，序列里的数均减去一个 $x$。

当序列极差为 $1$ 时，将其开方会有两种情况：

1.开完方之后序列极差为0，下次开根就是区间减法。

2.开完方之后极差为1，开根相当于均减1个数。

若极差大于1，则暴力开根。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>

using namespace std;

#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


const int N=1e5+5;\/\/注意修改
const int mod=1e9+7;
int a[N];
struct tree{
    int l,r;
    int sum;
    int add;
    int mx,mn;
}tr[N<<2];
void pushup(int rt){
    tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
    tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
    tr[rt].mn=min(tr[rt<<1].mn,tr[rt<<1|1].mn);
}
void pushdown(int rt){
    if(tr[rt].add==0) return ;
    tr[rt<<1].add+=tr[rt].add;
    tr[rt<<1].sum+=tr[rt].add*(tr[rt<<1].r-tr[rt<<1].l+1);
    tr[rt<<1|1].add+=tr[rt].add;
    tr[rt<<1|1].sum+=tr[rt].add*(tr[rt<<1|1].r-tr[rt<<1|1].l+1);
    tr[rt<<1].mx+=tr[rt].add;
    tr[rt<<1].mn+=tr[rt].add;
    tr[rt<<1|1].mx+=tr[rt].add;
    tr[rt<<1|1].mn+=tr[rt].add;
    tr[rt].add=0;
}
void build(int rt,int l,int r){
    tr[rt].l=l;
    tr[rt].r=r;
    tr[rt].add=0;
    if(l==r){
        tr[rt].sum=a[l];
        tr[rt].mx=a[l];
        tr[rt].mn=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void sub(int rt,int l,int r,int x){
    tr[rt].add-=x;
    tr[rt].mx-=x;
    tr[rt].mn-=x;
    tr[rt].sum-=x*(r-l+1);
}
void add(int rt,int l,int r,int k){
    \/\/cout<<rt<<" "<<l<<" "<<r<<endl;
    if(tr[rt].l>=l&&tr[rt].r<=r){
        tr[rt].add+=k;
        tr[rt].sum+=k*(tr[rt].r-tr[rt].l+1);
        tr[rt].mx+=k;
        tr[rt].mn+=k;
        return ;
    }
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    if(l<=mid) add(rt<<1,l,r,k);
    if(r>mid) add(rt<<1|1,l,r,k);
    pushup(rt);
}
int query(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        return tr[rt].sum;
    }
    if(tr[rt].l==tr[rt].r) return 0;
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    int res=0;
    if(l<=mid) res+=query(rt<<1,l,r);
    if(r>mid) res+=query(rt<<1|1,l,r);
    pushup(rt);
    return res;
}
void Sqrt(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        int Max=tr[rt].mx;
        int Min=tr[rt].mn;
        if(Max-Min<=1&&(int)sqrt(Max)-(int)sqrt(Min)==Max-Min){
            sub(rt,tr[rt].l,tr[rt].r,Max-(int)sqrt(Max));
            return ;
        }
    }
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    if(l<=mid) Sqrt(rt<<1,l,r);
    if(r>mid) Sqrt(rt<<1|1,l,r);
    pushup(rt);
}
signed main(){
    fst
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
\/\/    for(int i=1;i<=n<<2;i++){
\/\/        cout<<tr[i].sum<<" ";
\/\/    }
\/\/    cout<<endl;
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op;
        if(op==1){
            int k;
            cin>>x>>y>>k;
            add(1,x,y,k);
        }
        if(op==2){
            cin>>x>>y;
            Sqrt(1,x,y);
        }
        if(op==3){
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
        \/\/cout<<query(1,1,n)<<endl<<endl;
    }
}