摘要：
标题描述给出了一个长度为$n$的序列，并支持$m$操作。有三种操作：区间加法、区间开根和区间求和。对于原始的两个数字$a$和$b$，$sqrta$和$sqrtb$在生根后变为$sqrt$和$sqrtb$，它们的差值从$a-b$变为$sqrta-sqrtb$。还有$=a-b$，所以平方根之后的差值小于原始差值的平方根。因此，在一个间隔中生根$loglog$次后，不需要强制生根，可以直接缩短间隔。分析间隔添加操作：仅修改经过节点的势能，影响$log$节点，这些节点的势能将恢复为$loglog$。所以总的时间复杂度就是总势能$O$。
给出一个长度为 $n$ 的序列，支持 $m$ 次操作，操作有三种：区间加、区间开根、区间求和。
$n,m,a_ile 100000$ 。
题解
线段树+均摊分析
对于原来的两个数 $a$ 和 $b$ ( $a>b$ ) ，开根后变成 $sqrt a$ 和 $sqrt b$ ，它们的差从 $a-b$ 变成了 $sqrt a-sqrt b$ 。
又有 $(sqrt a-sqrt b)(sqrt a+sqrt b)=a-b$ ，因此开方后的差小于原来差的开方。
而当区间差为 $0$ 或 $a=x^2,b=x^2-1$ 的 $1$ 时，区间开根就变成了区间减。
因此一个区间开根 $loglog(Max-Min)$ 次后就不需要暴力开根，直接区间减即可。
定义线段树节点势能为 $loglog(Max-Min)$ ，那么每次对 $[l,r]$ 开根就是将所有 $lle x,yle r$ ，且势能不为 $0$ 的节点 $[x,y]$ 的势能减 $1$ ，代价为势能减少总量。
分析区间加操作：只会修改到经过的节点的势能，影响 $log$ 个节点，将这些点的势能恢复为 $loglog(Max-Min)$ 。
因此总的时间复杂度就是总势能量 $O((n+mlog n)loglog a)$ 。
#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 100010
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
using namespace std;
typedef long long ll;
ll sum[N << 2] , mx[N << 2] , mn[N << 2] , tag[N << 2];
inline void add(ll v , int l , int r , int x)
{
sum[x] += v * (r - l + 1) , mx[x] += v , mn[x] += v , tag[x] += v;
}
inline void pushup(int x)
{
sum[x] = sum[x << 1] + sum[x << 1 | 1];
mx[x] = max(mx[x << 1] , mx[x << 1 | 1]);
mn[x] = min(mn[x << 1] , mn[x << 1 | 1]);
}
inline void pushdown(int l , int r , int x)
{
if(tag[x])
{
int mid = (l + r) >> 1;
add(tag[x] , lson) , add(tag[x] , rson);
tag[x] = 0;
}
}
inline void build(int l , int r , int x)
{
if(l == r)
{
scanf("%lld" , &sum[x]) , mx[x] = mn[x] = sum[x];
return;
}
int mid = (l + r) >> 1;
build(lson) , build(rson);
pushup(x);
}
inline void update(int b , int e , ll a , int l , int r , int x)
{
if(b <= l && r <= e)
{
add(a , l , r , x);
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , a , lson);
if(e > mid) update(b , e , a , rson);
pushup(x);
}
inline void change(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e && mx[x] - (ll)sqrt(mx[x]) == mn[x] - (ll)sqrt(mn[x]))
{
add((ll)sqrt(mx[x]) - mx[x] , l , r , x);
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) change(b , e , lson);
if(e > mid) change(b , e , rson);
pushup(x);
}
inline ll query(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e) return sum[x];
pushdown(l , r , x);
int mid = (l + r) >> 1;
ll ans = 0;
if(b <= mid) ans += query(b , e , lson);
if(e > mid) ans += query(b , e , rson);
return ans;
}
int main()
{
int n , m , opt , x , y;
ll z;
scanf("%d%d" , &n , &m);
build(1 , n , 1);
while(m -- )
{
scanf("%d%d%d" , &opt , &x , &y);
if(opt == 1) scanf("%lld" , &z) , update(x , y , z , 1 , n , 1);
else if(opt == 2) change(x , y , 1 , n , 1);
else printf("%lld
" , query(x , y , 1 , n , 1));
}
return 0;
}