原题链接：数列分块入门5

$a$ 是序列，修改直接作用于序列；

$b_i$ 表示块 $i$ 若全为 $1$ 或 $0$ 的和

$f_i$ 表示块 $i$ 是否全为 $1$ 或 $0$

$id_i$ 表示第 $i$ 个数所属块的编号

My Code：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
inline ll read(){
	ll 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*10+ch-48;ch=getchar();}
	return x*f;
}
int n,len;
int a[N],f[N],id[N];
ll b[N];
void init(){
	len=sqrt(n);
	for(int i=1;i<=n;i++) id[i]=(i-1)/len+1;
}
void modify(int l,int r){
	int sid=id[l],eid=id[r];
	if(sid==eid){
		if(!f[sid]){
			for(int i=l;i<=r;i++) a[i]=sqrt(a[i]);
		}
		return ;
	}
	if(!f[sid])
		for(int i=l;id[i]==sid;i++) a[i]=sqrt(a[i]);
	for(int i=sid+1;i<eid;i++){
		int st=1+(i-1)*len,ed=min(n,i*len),flag=1;
		if(f[i]) continue;
		b[i]=0;
		for(int j=st;j<=ed;j++) a[j]=sqrt(a[j]),flag=(a[j]>1?0:1),b[i]+=a[j];
		if(flag) f[i]=1;
	}
	if(!f[eid])
		for(int i=r;id[i]==eid;i--) a[i]=sqrt(a[i]);
}
ll query(int l,int r){
	int sid=id[l],eid=id[r];
	ll ret=0;
	if(sid==eid){
		for(int i=l;i<=r;i++) ret+=a[i];
		return ret;
	}
	for(int i=l;id[i]==sid;i++) ret+=a[i];
	for(int i=sid+1;i<eid;i++){
		int st=1+(i-1)*len,ed=min(n,i*len);
		if(f[i]) ret+=b[i];
		else for(int j=st;j<=ed;j++) ret+=a[j];
	}
	for(int i=r;id[i]==eid;i--) ret+=a[i];
	return ret;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	init();
	for(int i=1;i<=n;i++){
		int opt=read(),l=read(),r=read(),c=read();
		if(opt==0) modify(l,r);
		else printf("%lld\n",query(l,r));
	}
	return 0;
}