题解 | #花神游历各国#

不需要懒标记，区间修改转为单点修改

思路

已知：0 或 1 开根号后 仍是 0 或 1，又因为 1e9  最多开 5 次根号就会变成 1（每个数最多修改 5 次）
所以本题的区间修改 可以变为单点修改 + 剪枝

为什么不会超时？

对于查询操作，单次查询时间复杂度为 O(logn)，最多执行 m 次，所以最坏是 O(m*logn)
对于修改操作，单点修改时间复杂度 O(logn)
又因为有剪枝，每个点最多修改 5 次，且 m 次操作，最多修改 n 个点，所以最坏是 O(5*n*logn)
所以总时间复杂度约为 max(O(m*logn),O(5*n*logn))   

flag 取值的含义

flag取值 0 ：[l,r]区间里的每个数都不再需要取根号：说明区间里的所有数要么是0，要嘛是1
flag取值 1 ：[l,r]区间里存在需要取根号的数

关于 modify 中的剪枝

剪枝：if(tr[u].flag==0) return ;  ( 我们令该语句为 (1) )

当语句 (1) 执行时，说明此时所在区间(结点) 里的每个数 ，要嘛为 0 ，要么为 1
即：取根号后值是不变的，所以就不需要对它们取根号了

参考题解：https://www.acwing.com/solution/content/6800/

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+10;

int w[N];
int n,m;
struct node{
    int l,r;
    ll sum;
    int flag;
}tr[N*4];

void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    tr[u].flag=max(tr[u<<1].flag,tr[u<<1|1].flag);
}

void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r) tr[u].sum=w[l],tr[u].flag=w[l]<=1?0:1;
    else{
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r){
    if(tr[u].flag==0) return ;  // 剪枝
    if(tr[u].l==tr[u].r) tr[u].sum=(ll)sqrt(tr[u].sum),tr[u].flag=tr[u].sum<=1?0:1;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r);
        if(r>mid) modify(u<<1|1,l,r);
        pushup(u);
    }
}

ll query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;

    int mid=tr[u].l+tr[u].r>>1;
    ll sum=0;
    if(l<=mid)  sum=query(u<<1,l,r);
    if(r>mid)   sum+=query(u<<1|1,l,r);

    return sum;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);

    scanf("%d",&m);
    while(m--){ 
        int x,l,r;
        scanf("%d %d %d",&x,&l,&r);
        if(x==1) printf("%lld\n",query(1,l,r));
        else modify(1,l,r);
    }    

    return 0;
}