题解 | #势能线段树模板题一#

思路

我们没有办法直接对区间进行开方然后下传，所以pushdown就没必要写了。
对于每个数，开方6次之后达到势能上限，其结果必然为0或者1。那么对于整个区间，
可以记录开方次数（取区间内开方次数最少的那个值）是否达到6就可以了，
或者只要一个区间全为0或1的话，也可以直接返回。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=2e5+7;

int n,m,op,l,r;
int tr[maxn<<2],cnt[maxn<<2];

void build(int node,int l,int r){
    if(l==r){
        cin>>tr[node];
        return;
    }
    int mid=l+r>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    tr[node]=tr[node<<1]+tr[node<<1|1];
    cnt[node]=cnt[node<<1]+cnt[node<<1|1];
}

int query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return tr[node];
    }
    int mid=l+r>>1,res=0;
    if(ql<=mid) res+=query(node<<1,l,mid,ql,qr);
    if(qr>mid) res+=query(node<<1|1,mid+1,r,ql,qr);
    return res;
}

void update(int node,int l,int r,int ql,int qr){
    if(cnt[node]>5) return;
    if(l==r){
        tr[node]=sqrt(tr[node]);
        cnt[node]++;
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid) update(node<<1,l,mid,ql,qr);
    if(qr>mid) update(node<<1|1,mid+1,r,ql,qr);
    tr[node]=tr[node<<1]+tr[node<<1|1];
    cnt[node]=min(cnt[node<<1],cnt[node<<1|1]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>op>>l>>r;
        if(op==1){
            update(1,1,n,l,r);
        }else{
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
    return 0;
}