考虑到一个数开根号 \(loglog\) 次后就会变成1，设某个Node的势能为 \(loglog(maxv-minv)\) ，那么一次根号操作会使得势能下降 \(1\) ，一次加操作最多增加 \(logloga\) 的势能。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400005;
ll sum[N],mx[N],mn[N],tag[N],src[N];
void add(ll p,ll l,ll r,ll v)
{
sum[p]+=v*(r-l+1);
mx[p]+=v;
mn[p]+=v;
tag[p]+=v;
}
void pushup(int p)
{
sum[p]=sum[p*2]+sum[p*2+1];
mx[p]=max(mx[p*2],mx[p*2+1]);
mn[p]=min(mn[p*2],mn[p*2+1]);
}
void pushdown(int p,int l,int r)
{
if(tag[p])
{
add(p*2,l,(l+r)/2,tag[p]);
add(p*2+1,(l+r)/2+1,r,tag[p]);
tag[p]=0;
}
}
void build(int p,int l,int r)
{
if(l==r)
{
sum[p]=mx[p]=mn[p]=src[l];
}
else
{
build(p*2,l,(l+r)/2);
build(p*2+1,(l+r)/2+1,r);
pushup(p);
}
}
void modify(int p,int l,int r,int ql,int qr,int v)
{
if(l>qr||r<ql) return;
if(l>=ql&&r<=qr)
{
add(p,l,r,v);
}
else
{
pushdown(p,l,r);
modify(p*2,l,(l+r)/2,ql,qr,v);
modify(p*2+1,(l+r)/2+1,r,ql,qr,v);
pushup(p);
}
}
void change(int p,int l,int r,int ql,int qr)
{
if(l>qr||r<ql) return;
if(l>=ql&&r<=qr && mx[p]-(ll)sqrt(mx[p]) == mn[p]-(ll)sqrt(mn[p]))
{
add(p,l,r,(ll)sqrt(mx[p])-mx[p]);
}
else
{
pushdown(p,l,r);
change(p*2,l,(l+r)/2,ql,qr);
change(p*2+1,(l+r)/2+1,r,ql,qr);
pushup(p);
}
}
ll query(int p,int l,int r,int ql,int qr)
{
if(l>qr||r<ql) return 0;
if(l>=ql&&r<=qr)
{
return sum[p];
}
else
{
pushdown(p,l,r);
return query(p*2,l,(l+r)/2,ql,qr) + query(p*2+1,(l+r)/2+1,r,ql,qr);
}
}
int main()
{
ios::sync_with_stdio(false);
int n,m,t1,t2,t3,t4;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>src[i];
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
cin>>t1>>t2>>t3;
if(t1==1)
{
cin>>t4;
modify(1,1,n,t2,t3,t4);
}
if(t1==2)
{
change(1,1,n,t2,t3);
}
if(t1==3)
{
cout<<query(1,1,n,t2,t3)<<endl;
}
}
}