loj #6281. 数列分块入门 5

题面

解题思路

区间开方，求和。分块，注意如果区间都是1要特判，否则会T

代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 50005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f; 
}

int n,num,l[MAXN],r[MAXN];
int siz,bl[MAXN],a[MAXN],sum[MAXN];
bool lazy[MAXN];

inline void build(){
    siz=sqrt(n)/3;
    num=n/siz;
    if(n%siz) num++;
    for(register int i=1;i<=num;i++){
        l[i]=(i-1)*siz+1;
        r[i]=i*siz;
    }
    r[num]=n;
    for(register int i=1;i<=n;i++)
        bl[i]=(i-1)/siz+1,sum[bl[i]]+=a[i];
}

inline void change(int x){
    lazy[x]=1;sum[x]=0;
    for(register int i=l[x];i<=r[x];i++){
        if(a[i]>1) lazy[x]=0;
        a[i]=sqrt(a[i]);
        sum[x]+=a[i];
    }
}

inline void update(int ql,int qr){
    if(bl[ql]==bl[qr]){
        if(lazy[bl[ql]]) return;
        for(register int i=ql;i<=qr;i++){
            sum[bl[i]]-=a[i];
            a[i]=sqrt(a[i]);
            sum[bl[i]]+=a[i];
        }
        return ;
    }
    for(register int i=ql;i<=r[bl[ql]];i++){
        sum[bl[i]]-=a[i];
        a[i]=sqrt(a[i]);
        sum[bl[i]]+=a[i];
    }
    for(register int i=l[bl[qr]];i<=qr;i++){
        sum[bl[i]]-=a[i];
        a[i]=sqrt(a[i]);
        sum[bl[i]]+=a[i];
    }
    for(register int i=bl[ql]+1;i<bl[qr];i++){
        if(lazy[i]) continue;
        change(i);
    }
}

inline int query(int x,int y){
    int ret=0;
    if(bl[x]==bl[y]){
        for(register int i=x;i<=y;i++) ret+=a[i];
        return ret;
    }
    for(register int i=x;i<=r[bl[x]];i++) ret+=a[i];
    for(register int i=l[bl[y]];i<=y;i++) ret+=a[i];
    for(register int i=bl[x]+1;i<bl[y];i++) ret+=sum[i];
    return ret;
}

int main(){
    n=rd();
    for(register int i=1;i<=n;i++) a[i]=rd();
    build();
    for(register int i=1;i<=n;i++){
        int op,x,y,z;
        op=rd();x=rd();y=rd();z=rd();
        if(op==0) update(x,y);
        else printf("%d
",query(x,y));
    }
    return 0;
}