题解：P13980 数列分块入门 5

Aventurine_ · 2025-09-07 11:21:01 · 题解

思路

这道题涉及到区间操作，所以我们自然可以想到线段树，区间求和很简单，主要在于怎么开方，注意到 0 \leq a_i \leq 2^{31}-1，用计算器算一下，最多 5 次开方就可以变成 1，之后再开方就没有作用了，所以我们可以记录区间最大值，如果最大值 >1，那么我们就暴力处理，否则可以直接跳过，注意 a_i 可以等于 0。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int n,m;
int a[N],mx[4*N],sum[4*N];
int ls(int nw){return nw<<1;}
int rs(int nw){return nw<<1|1;}
void push_up(int nw)
{
    mx[nw]=max(mx[ls(nw)],mx[rs(nw)]);
    sum[nw]=sum[ls(nw)]+sum[rs(nw)];
}
void build(int nw,int l,int r)
{
    if(l==r)
    {
        mx[nw]=a[l];
        sum[nw]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls(nw),l,mid);
    build(rs(nw),mid+1,r);
    push_up(nw);
}
void update(int nw,int l,int r,int lt,int rt)
{
    if(mx[nw]==1||mx[nw]==0)return;//注意可以等于0
    if(l==r)
    {
        sum[nw]=mx[nw]=sqrt(mx[nw]);return;
    }
    int mid=(l+r)>>1;
    if(lt<=mid)update(ls(nw),l,mid,lt,rt);
    if(rt>mid)update(rs(nw),mid+1,r,lt,rt);
    push_up(nw);
}
int query(int nw,int l,int r,int lt,int rt)
{
    int res=0;
    if(lt<=l&&rt>=r)return sum[nw];
    int mid=(l+r)>>1;
    if(lt<=mid)res+=query(ls(nw),l,mid,lt,rt);
    if(rt>mid)res+=query(rs(nw),mid+1,r,lt,rt);
    return res;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    m=n;
    while(m--)
    {
        int o,l,r;
        cin>>o>>l>>r;
        if(o==0)
        {
            update(1,1,n,l,r);
        }
        else{
            cout<<query(1,1,n,l,r)<<"\n";
        }
    }
    return 0;
}