题解——loj6281 数列分块入门5 （分块）

分块

若块内最大值为0或1，则不用再开方

然后暴力修改

可以证明，如果开方后向下取整，则最多开方4次一个数就会变成0或1

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long n,sz,num,belong[50010],a[50010],maxb[50010],sum[50010];
void calbe(int n){
    for(int i=1;i<=n;i++)    
        belong[i]=(i-1)/sz+1;
}
void reset(int x){
    maxb[x]=0;
    sum[x]=0;
    for(int i=(x-1)*sz+1;i<=min(sz*x,n);i++){
        maxb[x]=max(maxb[x],a[i]);
        sum[x]+=a[i];
        }
}
long long query(int l,int r){
    int xl=belong[l];
    int xr=belong[r];
    long long ans=0;
    for(int i=l;i<=min(xl*sz,(long long)r);i++)
        ans+=a[i];
    if(xl!=xr){
        for(int i=(xr-1)*sz+1;i<=r;i++)
            ans+=a[i];
    }   
    for(int i=xl+1;i<=xr-1;i++)
        ans+=sum[i];
    return ans;
}
void update(int l,int r){
    int xl=belong[l];
    int xr=belong[r];
    for(int i=l;i<=min(xl*sz,(long long)r);i++){
        a[i]=sqrt(a[i]);
        }
    reset(xl);
    if(xl!=xr){
        for(int i=(xr-1)*sz+1;i<=r;i++){
            a[i]=sqrt(a[i]);
            }
        reset(xr);
    }
    for(int i=xl+1;i<=xr-1;i++){
        if(maxb[i]<=1)
            continue;
        for(int j=(i-1)*sz+1;j<=i*sz;j++)
            a[j]=sqrt(a[j]);
        reset(i);
    }
}
int main(){
    scanf("%lld",&n);
    sz=sqrt(n);
    num=n/sz;
    if(n%sz)
        num++;
    calbe(n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=num;i++)
        reset(i);
    for(int i=1;i<=n;i++){
        int opt,l,r,c;
        scanf("%d %d %d %d",&opt,&l,&r,&c);
        if(opt==0)
            update(l,r);
        else
            printf("%lld
",query(l,r));
    } 
    return 0;
}