Description
Input
Output
每次x=1时，每行一个整数，表示这次旅行的开心度
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
Solution
一个数最多只会被开根$loglog$次（因为每次开根相当于指数除$2$）。
然后用线段树维护一个区间和和区间最大值，如果这个区间的最大值小于等于$1$就没有做的必要了。
去年这个题写了个分块在$BZOJ$被卡了之后就扔着不管了……
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N (100009)
#define LL long long
using namespace std; struct Sgt{LL max,sum;}Segt[N<<];
int n,m,a[N],opt,x,y; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} void Build(int now,int l,int r)
{
if (l==r) {Segt[now].max=a[l]; Segt[now].sum=a[l]; return;}
int mid=(l+r)>>;
Build(now<<,l,mid); Build(now<<|,mid+,r);
Segt[now].sum=Segt[now<<].sum+Segt[now<<|].sum;
Segt[now].max=max(Segt[now<<].max,Segt[now<<|].max);
} void Update(int now,int l,int r,int l1,int r1)
{
if (Segt[now].max<= || l>r1 || r<l1) return;
if (l==r) {Segt[now].max=Segt[now].sum=sqrt(Segt[now].sum); return;}
int mid=(l+r)>>;
Update(now<<,l,mid,l1,r1); Update(now<<|,mid+,r,l1,r1);
Segt[now].sum=Segt[now<<].sum+Segt[now<<|].sum;
Segt[now].max=max(Segt[now<<].max,Segt[now<<|].max);
} LL Query(int now,int l,int r,int l1,int r1)
{
if (l>r1 || r<l1) return ;
if (l1<=l && r<=r1) return Segt[now].sum;
int mid=(l+r)>>;
return Query(now<<,l,mid,l1,r1)+Query(now<<|,mid+,r,l1,r1);
} int main()
{
n=read();
for (int i=; i<=n; ++i) a[i]=read();
Build(,,n);
m=read();
while (m--)
{
opt=read(); x=read(); y=read();
if (opt==) printf("%lld\n",Query(,,n,x,y));
else Update(,,n,x,y);
}
}