[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
",query(x,y));
    }
    return 0;
}