由题意可知，每一个点最多可以被更新63次之后就不会继续更新了。。。
所以记录一个区间最大值，如果区间最大值等于1，那么就不继续更新下去了。
between the X-th and Y-th：意味着x可能大于y。
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 110000
#define mem(a,b) (memset(a),b,sizeof(a))
#define lmin 1
#define rmax n
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define now l,r,rt
#define int_now int l,int r,int rt
#define INF 99999999
#define LL __int64
#define mod 10007
#define eps 1e-6
#define zero(x) (fabs(x)<eps?0:x)
LL maxx[maxn*4];
LL sum[maxn*4];
LL val[maxn*4];
void push_up(int_now)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
void creat(int_now)
{sum[rt]=val[rt]=0;if(l!=r){creat(lson);creat(rson);push_up(now);return;}scanf("%I64d",&val[rt]);sum[rt]=maxx[rt]=val[rt];
}
void updata(int ll,int rr,int_now)
{if(ll>r||rr<l)return ;if(maxx[rt]==1)return;if(l==r){val[rt]=sqrt(val[rt]);maxx[rt]=sum[rt]=val[rt];return;}updata(ll,rr,lson);updata(ll,rr,rson);push_up(now);
}
LL query(int ll,int rr,int_now)
{if(ll>r||rr<l)return 0;if(ll<=l&&rr>=r)return sum[rt];return query(ll,rr,lson)+query(ll,rr,rson);
}
int main()
{int cas=0;int n,q,t,l,r;while(~scanf("%d",&n)){cas++;creat(root);scanf("%d",&q);printf("Case #%d:\n",cas);while(q--){scanf("%d%d%d",&t,&l,&r);if(l>r)swap(l,r);if(t==0){updata(l,r,root);}else printf("%I64d\n",query(l,r,root));}cout<<endl;}return 0;
}