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

Sample Output

101
11
11

HINT

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

题目分析：

一看到区间求和就想到树状数组||线段树来搞 但是开根号这种东西很难打标记
因为data[i]<10^9 开5~6次根号就变成1了 我们可以用暴力修改，同时维护并查集fa[i]指向后面第一个不为1的数，跳着更改就可以大大减少时间。同时维护树状数组等就可以实现区间和查询了。
没想到还是道双倍经验的题QAQ

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long f[110000];
int val[110000];
int fa[110000];
int n,m;
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void update(int x,int c)
{
    for(;x<=n;x+=x&-x) f[x]+=c;
}
long long ask(int x)
{
    if(x==0) return 0;
    long long sum=0;
    for(;x;x-=x&-x) sum+=f[x];
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]),update(i,val[i]);
    for(int i=1;i<=n+10;i++) fa[i]=i;
    scanf("%d",&m);
    for(int k=1;k<=m;k++)
    {
        int temp,x,y;
        scanf("%d%d%d",&temp,&x,&y);
        if(temp==2)
        {
            for(int i=x;i<=y;i=find(i+1))
            {
                update(i,(int)sqrt(val[i])-val[i]);
                val[i]=(int)sqrt(val[i]);
                if(val[i]<=1) fa[i]=find(i+1);
            }
        }
        else printf("%lld\n",ask(y)-ask(x-1));
    }
    return 0;
}