题解

显然线段树，最多开方6次，所以加个max剪枝

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,a[1005],sum[4005],mx[4005];  // a:原始数组 sum:区间和 mx:区间最大值
void build(int l,int r,int id)  // 建树 l,r:当前区间 id:节点编号
{
    if (l==r)  // 叶子节点
    {
        sum[id]=mx[id]=a[l];  // 初始化区间和和最大值
        return;
    }
    int mid=(l+r)>>1;  // 计算中点
    build(l,mid,id<<1);  // 递归建左子树
    build(mid+1,r,id<<1|1);  // 递归建右子树
    sum[id]=sum[id<<1]+sum[id<<1|1];  // 上传区间和
    mx[id]=max(mx[id<<1],mx[id<<1|1]);  // 上传区间最大值
}
void update(int l,int r,int ql,int qr,int id)  // 区间开方更新
{
    if (mx[id]==1)  // 优化:区间最大值已经是1，不需要开方
        return;
    if (l==r) //最多开方6次，所以先暴力递归到叶子节点
    {
        a[l]=sqrt(a[l]),sum[id]=a[l],mx[id]=a[l];  // 叶子节点直接开方并更新
        return;
    }
    int mid=(l+r)>>1;  // 计算中点
    if (ql<=mid) update(l,mid,ql,qr,id<<1);  // 更新左子树
    if (qr>mid) update(mid+1,r,ql,qr,id<<1|1);  // 更新右子树
    sum[id]=sum[id<<1]+sum[id<<1|1],mx[id]=max(mx[id<<1],mx[id<<1|1]);  // 上传信息
}
int query(int l,int r,int ql,int qr,int id)  // 区间和查询
{
    if (ql<=l && qr>=r)  // 当前区间完全包含在查询区间内
        return sum[id];  // 直接返回区间和
    int mid=(l+r)>>1,s=0;  // 计算中点，初始化结果
    if (ql<=mid) s+=query(l,mid,ql,qr,id<<1);  // 查询左子树
    if (qr>mid) s+=query(mid+1,r,ql,qr,id<<1|1);  // 查询右子树
    return s;  // 返回区间和
}
signed main()
{
	cin >> n;  // 读入数列长度
    for (int i=1;i<=n;i++)
        cin >> a[i];  // 读入初始数列
    cin >> m;  // 读入操作次数
    build(1,n,1);  // 建线段树
    int k,x,y;
    while (m--)  // 处理每个操作
    {
        cin >> k >> x >> y;  // 读入操作类型和区间
        if (k==0)  // 区间开方操作
            update(1,n,x,y,1);
        else  // 区间查询操作
            cout << query(1,n,x,y,1) << endl;  // 输出区间和
    }
	return 0;
}