[LOJ] 分块九题 5

区间开平方，区间查询。
lazy标记改为区间是否全是1或者0，这样的区间是没有更新价值的。
//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cctype>

#define sq(x) (floor(sqrt(x)))

using namespace std;

const int MAXN=500005;

inline int read_d(){

    int ret=0,op=1;char c;

    while(c=getchar(),!isdigit(c))op=c=='-'?-1:1;

    while(isdigit(c)){

        ret=ret*10+c-'0';

        c=getchar();

    }

    return ret*op;

} 

int n;

int sum[MAXN],a[MAXN];

bool lazy[MAXN];

int l[MAXN],r[MAXN],bl[MAXN];

int block,num;

void build(){

    block=sqrt(n);

    num=n/block;

    if(n%block) num++;

    for(int i=1;i<=n;i++){

        l[i]=(i-1)*block+1;

        r[i]=i*block;

        bl[i]=(i-1)/block+1;

        sum[bl[i]]+=a[i];

    }

}

void updata_block(int id){

    lazy[id]=1;sum[id]=0;

    for(int i=l[id];i<=r[id];i++){

        if(a[i]>=2) lazy[id]=0;

        a[i]=sq(a[i]);

        sum[id]+=a[i];

    }

}

void updata(int x,int y){

    if(bl[x]==bl[y]){

        if(lazy[bl[x]]) return;

        for(int i=x;i<=y;i++){

            sum[bl[i]]-=a[i];

            a[i]=sq(a[i]);

            sum[bl[i]]+=a[i];

        }

        return;

    }

    for(int i=x;i<=r[bl[x]];i++){

        sum[bl[i]]-=a[i];

        a[i]=sq(a[i]);

        sum[bl[i]]+=a[i];

    }

    for(int i=l[bl[y]];i<=y;i++){

        sum[bl[i]]-=a[i];

        a[i]=sq(a[i]);

        sum[bl[i]]+=a[i];

    }

    for(int i=bl[x]+1;i<=bl[y]-1;i++){

        if(lazy[i]) continue;

        updata_block(i);

    }

}

int query(int x,int y){

    int ret=0;

    if(bl[x]==bl[y]){

        for(int i=x;i<=y;i++) ret+=a[i];

        return ret;

    }

    for(int i=x;i<=r[bl[x]];i++) ret+=a[i];

    for(int i=l[bl[y]];i<=y;i++) ret+=a[i];

    for(int i=bl[x]+1;i<=bl[y]-1;i++) ret+=sum[i];

    return ret;

}

int main(){

    n=read_d();

    for(int i=1;i<=n;i++) a[i]=read_d();

    build();

    for(int i=1;i<=n;i++){

        int q=read_d(),x=read_d(),y=read_d(),z=read_d();

        if(q==0) updata(x,y);

        else printf("%d\n",query(x,y));

    }

    return 0;

}
巴特西

[LOJ] 分块九题 5

最新文章

热门文章
