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