# LOJ#6281. 数列分块入门 5

2018-02-13 10:06:02来源:cnblogs.com作者:自为风月马前卒人点击

#### 样例输入

``41 2 2 30 1 3 11 1 4 40 1 2 21 1 2 4``

#### 样例输出

``62``

#### 数据范围与提示

`#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#define int long long using namespace std;const int MAXN=1e5+10;const int INF=1e8+10;inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}    return x*f;}int N;int a[MAXN],block,L[MAXN],R[MAXN],belong[MAXN],sum[MAXN],flag[MAXN];void Sqrt(int l,int r){	for(int i=l;i<=min(r,R[l]);i++)	{		sum[belong[i]]-=a[i];		a[i]=sqrt(a[i]);		sum[belong[i]]+=a[i];	}	if(belong[l]!=belong[r])		for(int i=L[r];i<=r;i++)sum[belong[i]]-=a[i],a[i]=sqrt(a[i]),sum[belong[i]]+=a[i];	for(int i=belong[l]+1;i<=belong[r]-1;i++)	{		if(flag[i]) {continue;}		flag[i]=1;		for(int j=L[i*block];j<=R[i*block];j++)		{sum[i]-=a[j];a[j]=sqrt(a[j]);sum[i]+=a[j];if(a[j]>1) flag[i]=0;		}	}}int Query(int l,int r){	int ans=0;	for(int i=l;i<=min(r,R[l]);i++)		ans+=a[i];	if(belong[l]!=belong[r])		for(int i=L[r];i<=r;i++)ans+=a[i];	for(int i=belong[l]+1;i<=belong[r]-1;i++)		ans+=sum[i];	return ans;}main(){    #ifdef WIN32    freopen("a.in","r",stdin);   // freopen("b.out","w",stdout);    #else    #endif	N=read();block=sqrt(N);	for(int i=1;i<=N;i++) a[i]=read();	for(int i=1;i<=N;i++) belong[i]=(i-1)/block+1,L[i]=(belong[i]-1)*block+1,R[i]=belong[i]*block;	for(int i=1;i<=N;i++) sum[belong[i]]+=a[i];	for(int i=1;i<=N;i++)	{		int opt=read(),l=read(),r=read(),c=read();		if(opt==0) Sqrt(l,r); 		else  printf("%d/n",Query(l,r));	}    return 0;}`