懒标记可向上传（线段树之开根号操作）

题目：n个数，m次询问，1为对区间所有数开根号，2为询问区间和

操前结果：a+b+c
操后结果：根号a + 根号b + 根号c   //可以在草稿纸上写写，电脑打不出根号
比较操前结果和操后结果，发现没有联系（不好维护）
但是可以发现a[i]的范围在int内
int为10^31-1,但可以把它看作10^32
而10^32开6次方，就变成1了
所以每次操作时，直接暴力给每个数开，再维护
最坏情况，每个数开6次即 O(6nlgn) 【复杂度可接受】,然后每个数都开成了1
然后都开成1时，每次ask即为目标区间长度

因其操前结果和操后结果现没有联系，所有tree[p]直接为区间和（上面说了暴力维护也是求和）
ly[p]为区间内所有的数是否开够6次

//

线段树就是要边操作边维护，不然就失去了意义，
而lazy[p]是延迟操作，但当前的tree[p]的值要维护好（即值要正确）
懒标记既可以向下传，也可以向上传
pushdown是向下传
此题是向上传（利用递归自带的回溯向上传）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n,m;
int a[N];
int ly[N<<2];
ll tr[N<<2];
void bulid(int p,int l,int r){
    if(l==r){ tr[p]=a[l];return ; }
    int mid=(l+r) >> 1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tr[p] = tr[p*2] + tr[p*2+1] ;
} 
void change(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        if(ly[p]>=6) return ;
        if(l==r){
            tr[p]=sqrt(tr[p]);
            ly[p]++;
            return ;
        } 
    }
    int mid=(l+r) >> 1;
    if(x<=mid) change(p*2,l,mid,x,y);
    if(y>=mid+1) change(p*2+1,mid+1,r,x,y);
    tr[p]=tr[p*2]+tr[p*2+1];
    if(ly[p*2]>=6&&ly[p*2+1]>=6) ly[p]=6; 
}
int ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        if(ly[p]>=6) return r-l+1;
        return tr[p];
    }
    int mid = (l+r) >> 1;
    ll res=0;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(mid+1<=y) res+=ask(p*2+1,mid+1,r,x,y);
    return res;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    bulid(1,1,n);
    while(m--){
        int op,x,y;
        cin >> op >> x >> y;
        if(op==1){
            change(1,1,n,x,y);
        }
        else cout << ask(1,1,n,x,y) << "\n";
    }
    return 0;
}