洛谷4145 花神游历各国

这似乎是个很经典的题，但因为我很菜所以现在才做。

显然，一个 $\le 10^{5}$ 的数最多经过 $6$ 次开方就一定可以变成 $1$ ，所以我们可以用线段树对每次询问进行单点修改，如果区间最大值 $\le 1$ 就不需要进行修改了。

这样最多每个数修改 $6$ 次，查询直接区间查询，总时间复杂度是 $O(n\times \log n + 6n)$ 。

struct Tree{
    ll left,right,sum,mx; 
} tree[400005];
ll s[100005],n,m,a,b,c;

inline void pushup(ll x)
{
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
    tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
}

void build(ll x,ll l,ll r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l==1) tree[x].sum=tree[x].mx=s[l];
    else
    {
        ll mid=(l+r)>>1;
        build(x*2,l,mid);
        build(x*2+1,mid,r);
        pushup(x);
    }
}

void update(ll x,ll l,ll r)
{
    if (tree[x].mx<=1) return;
    if (tree[x].right-tree[x].left==1)
    {
        tree[x].sum=sqrt(tree[x].sum);
        tree[x].mx=sqrt(tree[x].mx);
    }
    else
    {
        ll mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x*2,l,r);
        if (r>mid) update(x*2+1,l,r);
        pushup(x);
    }
}

ll query(ll x,ll l,ll r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].sum;
    else
    {
        ll ans=0,mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) ans+=query(x*2,l,r);
        if (r>mid) ans+=query(x*2+1,l,r);
        return ans;
    }
}

int main()
{
    n=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    build(1,1,n+1);
    m=read();
    for (ll i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        if (b>c) swap(b,c);
        if (a==0) update(1,b,c+1);
        else printf("%lld\n",query(1,b,c+1));
    }
    return 0;
}