P13980 数列分块入门 5 题解

_•́へ•́╬_ · 2025-09-06 12:54:06 · 题解

思路

一个数 x>1，被开方 \log\log x 次就会变成 1，因为开方就相当于指数除以 2，即 \large 10^{\log_{10}x} 变成 \large 10^\frac{\log_{10}x}{2}。之后会保持 1 不变。

暴力处理每次有意义的开方，一共也就 n\log\log V 次。一个区间的最大值 \leq1，就跳过不处理。

实现

写线段树。

#include<stdio.h>
#include<math.h>
#define N 524288
#define lc ((i)<<1|1)
#define rc ((i)+1<<1)
inline char nc()
{
    static char*l,*r,buf[99999];
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,maxn[N<<1];long long sum[N<<1];
inline int max(int x,int y){return x>y?x:y;}
inline void build(int i,int l,int r)
{
    if(l==r){read(maxn[i]);sum[i]=maxn[i];return;}
    int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
    sum[i]=sum[lc]+sum[rc];maxn[i]=max(maxn[lc],maxn[rc]);
}
inline void work(int i,int l,int r,int ql,int qr)
{
    if(qr<l||r<ql||maxn[i]<=1)return;
    if(l==r){maxn[i]=sum[i]=sqrt(maxn[i]);return;}
    int mid=l+r>>1;work(lc,l,mid,ql,qr);work(rc,mid+1,r,ql,qr);
    sum[i]=sum[lc]+sum[rc];maxn[i]=max(maxn[lc],maxn[rc]);
}
inline long long qry(int i,int l,int r,int ql,int qr)
{
    if(qr<l||r<ql)return 0;
    if(ql<=l&&r<=qr)return sum[i];
    int mid=l+r>>1;return qry(lc,l,mid,ql,qr)+qry(rc,mid+1,r,ql,qr);
}
main()
{
    read(n);build(0,0,n-1);
    for(int i=n,o,l,r;i--;)if(read(o),read(l),read(r),--l,--r,o)
        printf("%lld\n",qry(0,0,n-1,l,r));
    else work(0,0,n-1,l,r);
}