区间开平方，区间查询。
lazy标记改为区间是否全是1或者0，这样的区间是没有更新价值的。
//Stay foolish,stay hungry,stay young,stay simple#include#include #include #include #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;}