题目大意：区间开方求和（线段树）

思路：常规（一个节点如果全都是1了就book它以下，以后不管）

问题：提交并修改，若干次，每次都在第一个测试点显示tle

向大家表示真诚的感激

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int a[N],t[N],book[N],_case=0;
void read(int &p){
    int x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    p=x;
}
void pushup(int k){
	t[k]=t[k<<1]+t[k<<1|1];
	book[k]=book[k<<1]&&book[k<<1|1];
}
void build(int l,int r,int k){
	if(l==r){
		t[k]=a[l];
		book[k]=(a[l]==1);
	}
	else {
		int mid=(l+r)/2;
		build(l,mid,k<<1);
		build(mid+1,r,k<<1|1);
		pushup(k);
	}
}
void updata(int L,int R,int l,int r,int k){
	if(l==r){
		t[k]=sqrt(t[k]);
		book[k]=(t[k]==1);
	}
	else {
		int mid=(l+r)/2;
		if(L<=mid && !book[k<<1]) updata(L,R,l,mid,k<<1);
		if(R>mid && !book[k<<1|1]) updata(L,R,mid+1,r,k<<1|1);
		pushup(k);
	}
}
int query(int L,int R,int l,int r,int k){
	if(L<=l && r<=R) return t[k];
	else {
		int mid=(l+r)/2,res=0;
		if(L<=mid) res+=query(L,R,l,mid,k<<1);
		if(R>mid) res+=query(L,R,mid+1,r,k<<1|1);
		return res;
	}
}
void work(int n){
	printf("Case #%d:\n",++_case);
	int m,opt,l,r;
	for(int i=1;i<=n;i++) read(a[i]);
	build(1,n,1);
	read(m);
	while(m--){
		read(opt),read(l),read(r);
		if(opt==0) updata(l,r,1,n,1);
		else printf("%d\n",query(l,r,1,n,1));
	}
}
signed main()
{
	int n;
	while(~scanf("%d",&n)){
		work(n);
		puts("");
	}
	return 0;
}