原题链接

题解

1.由于每个点最多修改6次，所以我们可以暴力循环遍历所有点进行修改。然后可以把无需再修改的点跳过，即并查集，指向右端第一个仍然需要修改的值的下标
这样就是单点修改加区间查询，树状数组
时间复杂度 \(6·n·log(n)\)（单点修改）+ \(m·2·log(n)\) (区间查询)

code

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))

int a[100005];
int fa[100005];
int tree[100005]={0};
int n;

int finds(int now){return now==fa[now]?now:fa[now]=finds(fa[now]);}

void update(int x,int val)
{
    while(x<=n)
    {
        tree[x]+=val;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int sum=0;
    while(x)
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        update(i,a[i]);
        fa[i]=i;
    }
    int m;
    cin>>m;
    while(m--)
    {
        int k,l,r;
        cin>>k>>l>>r;
        if(l>r) swap(l,r);
        if(k==0)
        {
            for(int i=l;i<=r&&i>=l;i=finds(i+1))
            {
                //printf("i:%d\n",i);
                int d=sqrt(a[i]);
                update(i,d-a[i]);
                a[i]=d;
                if(a[i]<=1) fa[i]=i+1;
            }
        }
        else
        {
            cout<<query(r)-query(l-1)<<endl;
        }
    }
    return 0;
}