以为是很简单的维护区间和,但是修改的操作并不是简单的单点加或者区间加,而是把单点的值sqrt,就导致了没有办法使用
带add标记的区间修改,所以考虑优化单点修改,对于一个单点,最多修改5次即可,在区间修改中只修改叶子节点,然后进行push_
up,通过节点的bool变量判断此节点是否需要修改;
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    int l,r;
    long long sum;
    bool j;
}t[4*N];
int a[N];
void push_up(node&rt,node&ls,node&rs )
{
    rt.sum=ls.sum+rs.sum;
    rt.j=ls.j&&rs.j;
}
void push_down(int k)
{

}
void mark(node&rt,int val)
{
    rt.sum=sqrt(rt.sum);
    rt.j=rt.sum<=1;
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        t[k]={l,r,a[l],a[l]<=1};
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    t[k].l=l,t[k].r=r,t[k].j=0;
    push_up(t[k],t[k<<1],t[k<<1|1]);
}
void modify(int k,int x,int y,int val)
{
    if(t[k].j)
    {
        return;
    }
    if (x > y) return;
    if (t[k].l == t[k].r ) return mark(t[k], val);
    push_down(k);
    int mid = (t[k].l + t[k].r) / 2;
    if (x <= mid) modify(k << 1, x, y, val);
    if (y > mid) modify(k << 1 | 1, x, y, val);
    push_up(t[k], t[k << 1], t[k << 1 | 1]);
}
node query(int k,int x,int y)
{
    if (x <= t[k].l && t[k].r <= y) return t[k];
    push_down(k);
    int mid = (t[k].l + t[k].r) / 2;
    if (y <= mid) return query(k << 1, x, y);
    else if (x > mid) return query(k << 1 | 1, x, y);
    else
    {
        node L = query(k << 1, x, y), R = query(k << 1 | 1, x, y);
        node rt;
        push_up(rt, L, R);
        return rt;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int n;
     scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    int m;
     scanf("%d",&m);
    while(m--)
    {
        int op,x,y;
         scanf("%d %d %d",&op,&x,&y);
        if(op==1)
        {
            printf("%lld\n",query(1,x,y).sum);
        }else
        {

                modify(1,x,y,0);

        }
    }
    return 0;
}