首先呢,我们想到一种数据结构可以区间开方,一看就不行,但是一看就算是10^18开六次方也只剩一,就不用开根了,所以可以想到用线段树或者分块水过,由于本人 不会用分块,只能用常数巨大的线段树
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
typedef long long ll;
ll a[N];
int cnt,n;
struct node{
ll sum,maxm;
}tr[N<<];
inline void build(int k,int l,int r){
if(l==r) return tr[k].sum=tr[k].maxm=a[l],void();
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
tr[k].maxm=max(tr[k<<].maxm,tr[k<<|].maxm);
}
inline void change(int k,int l,int r,int x,int y){//连下放标记都不用,直接单点修改
if(r<x||l>y)return;
if(l==r) return tr[k].sum=tr[k].maxm=sqrt(tr[k].sum),void();
int mid=(l+r)>>;
if(tr[k<<].maxm>)change(k<<,l,mid,x,y);
if(tr[k<<|].maxm>)change(k<<|,mid+,r,x,y);
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
tr[k].maxm=max(tr[k<<].maxm,tr[k<<|].maxm);
}
inline ll query(int k,int l,int r,int x,int y){
if(l>y||r<x)return ;
if(x<=l&&r<=y)return tr[k].sum;
int mid=(l+r)>>;
return query(k<<,l,mid,x,y)+query(k<<|,mid+,r,x,y);
}
int main(){
int m,t,x,y;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
build(,,n);//初始化不要忘记
scanf("%d",&m);
printf("Case #%d:\n",++cnt);
while(m--){
scanf("%d%d%d",&t,&x,&y);
if(x>y)swap(x,y);//要求
if(t)printf("%lld\n",query(,,n,x,y));
else change(,,n,x,y);
}
puts("");
}
}