学步园

/*
分析：
    线段树。一开始没有想出来，不过仔细想想也就是了，一个
2^64的数，最多开7次平方，取整的话，就成1了，so。。。

                                                                                      2012-10-13
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
struct seg
{
	int l,r,mid;
	int flag_1;
	__int64 sum;
}T[300011];
__int64 num[100011];
void build(int l,int r,int k)
{
	T[k].l=l;
	T[k].r=r;
	T[k].mid=(l+r)>>1;
	T[k].flag_1=0;

	if(l==r)
	{
		T[k].sum=num[l];
		if(num[l]<=1)	T[k].flag_1=1;
		return ;
	}

	build(l,T[k].mid,2*k);
	build(T[k].mid+1,r,2*k+1);
	T[k].sum=T[2*k].sum+T[2*k+1].sum;
	if(T[2*k].flag_1 && T[2*k+1].flag_1)	T[k].flag_1=1;
}
void update(int l,int r,int k)
{
	if(T[k].flag_1)	return ;

	if(T[k].l==l && T[k].r==r && l==r)
	{
		T[k].sum=(__int64)sqrt(1.0*T[k].sum);
		if(T[k].sum<=1)	T[k].flag_1=1;
		return ;
	}

	if(r<=T[k].mid)		update(l,r,2*k);
	else if(l>T[k].mid)	update(l,r,2*k+1);
	else
	{
		update(l,T[k].mid,2*k);
		update(T[k].mid+1,r,2*k+1);
	}

	T[k].sum=T[2*k].sum+T[2*k+1].sum;
	if(T[2*k].flag_1 && T[2*k+1].flag_1)	T[k].flag_1=1;
}
__int64 find(int l,int r,int k)
{
	__int64 ans=0;

	if(T[k].l==l && T[k].r==r)	return T[k].sum;

	if(r<=T[k].mid)		ans+=find(l,r,2*k);
	else if(l>T[k].mid)	ans+=find(l,r,2*k+1);
	else
	{
		ans+=find(l,T[k].mid,2*k);
		ans+=find(T[k].mid+1,r,2*k+1);
	}
	return ans;
}
int main()
{
	int Case=1;
	int n,m;
	int i;
	int a,b,c,x,y;
	while(scanf("%d",&n)!=-1)
	{
		for(i=1;i<=n;i++)	scanf("%I64d",&num[i]);
		build(1,n,1);

		scanf("%d",&m);
		printf("Case #%d:\n",Case++);
		while(m--)
		{
			scanf("%d%d%d",&c,&a,&b);
			x=a>b?b:a;
			y=a>b?a:b;
			if(c)	printf("%I64d\n",find(x,y,1));
			else	update(x,y,1);
		}
		printf("\n");
	}
	return 0;
}