题解：P13980 数列分块入门 5

KMYC · 2025-09-06 16:47:09 · 题解

注意到对 1 做开平方操作是没有意义的，而序列中最大的数只有 2^{31} - 1。5 次开平方操作后就会变成 1。

所以对于每一个修改操作，当一个区间的最大值是 1 那么这个区间就不用做了。然后直接用线段树暴力修改每一个有意义的区间就好了。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=300010;
int n,a[N];
struct segtree{
    int sum,mx;
}t[N<<2];
void build(int p,int l,int r){
    if(l==r){
        t[p].sum=a[l];
        t[p].mx=a[l];
        return;
    }
    int lson=p<<1,rson=p<<1|1,mid=l+(r-l)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    t[p].sum=t[lson].sum+t[rson].sum;
    t[p].mx=max(t[lson].mx,t[rson].mx);
}
void update(int p,int l,int r,int ul,int ur){
    if(l==r){
        t[p].mx=sqrt(t[p].mx);
        t[p].sum=sqrt(t[p].sum);
        return;
    }
    int lson=p<<1,rson=p<<1|1,mid=l+(r-l)/2;
    if(ul<=mid&&t[lson].mx>1) update(lson,l,mid,ul,ur);
    if(ur>mid&&t[rson].mx>1) update(rson,mid+1,r,ul,ur);
    t[p].sum=t[lson].sum+t[rson].sum;
    t[p].mx=max(t[lson].mx,t[rson].mx);
}
int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return t[p].sum;
    int lson=p<<1,rson=p<<1|1,mid=l+(r-l)/2;
    int res=0;
    if(ql<=mid) res+=query(lson,l,mid,ql,qr);
    if(qr>mid) res+=query(rson,mid+1,r,ql,qr);
    return res;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    int q=n;
    while(q--){
        int opt,l,r; cin>>opt>>l>>r;
        if(opt==0) update(1,1,n,l,r);
        else cout<<query(1,1,n,l,r)<<endl;
    }
    return 0;
}