提供一种数据结构，支持区间求和，以及区间开根号。
这种题一般暴力谁都能打，主要是练线段树。
下面给出两种解法：
第一种，额外维护区间最大值。
由于1、0开根是其本身，开根没有意义，我们维护区间最大值，如果区间最大值已经为1或0则直接return，否则继续向下开根。
剩下的维护区间和就可以了。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #define ll long long using namespace std; struct Sengment_Tree{ int l,r; ll sum,maxn; }t[400200]; int n,m; ll read(){ ll sum=0;int f=1;char x=getchar(); while(x<'0'||x>'9'){ if(x=='-') f=-1; x=getchar(); }while(x>='0'&&x<='9'){ sum=sum*10+x-'0'; x=getchar(); }return sum*f; } void updata(int p){ t[p].sum=t[p<<1].sum+t[p<<1|1].sum; t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn); } void build(int p,int l,int r){ t[p].l=l;t[p].r=r; if(l==r){ t[p].sum=t[p].maxn=read(); return; } int mid=l+r>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); updata(p); } void change(int p,int l,int r){ if(t[p].maxn<=1) return ; if(t[p].l==t[p].r){ t[p].sum=t[p].maxn=(ll)sqrt(t[p].sum); return ; } int mid=t[p].l+t[p].r>>1; if(l<=mid) change(p<<1,l,r); if(r>mid) change(p<<1|1,l,r); updata(p); } ll ask(int p,int l,int r){ if(l<=t[p].l&&t[p].r<=r) return t[p].sum; int mid=t[p].l+t[p].r>>1; ll ans=0; if(l<=mid) ans+=ask(p<<1,l,r); if(r>mid) ans+=ask(p<<1|1,l,r); return ans; } int main(){ int x,y,z; n=read(); build(1,1,n); m=read(); for(int i=1;i<=m;i++){ x=read();y=read();z=read(); if(x==1) printf("%lld ",ask(1,y,z)); else change(1,y,z); }return 0; }
第二种，维护lazy，表示是否已经全是1或0。
如果是，则直接return，否则继续向下开根。
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<queue> #define ll long long using namespace std; struct Sengment_Tree{ int l,r,flag; ll sum; }t[400200]; ll read(){ ll sum=0;int f=1;char x=getchar(); while(x<'0'||x>'9'){ if(x=='-') f=-1; x=getchar(); }while(x>='0'&&x<='9'){ sum=sum*10+x-'0'; x=getchar(); }return sum*f; } int n,qnum; ll a[100050]; void updata(int p){ t[p].sum=t[p<<1].sum+t[p<<1|1].sum; t[p].flag=t[p<<1].flag&t[p<<1|1].flag; } void build(int p,int l,int r){ t[p].l=l;t[p].r=r; if(l==r){ t[p].sum=a[l]; if(a[l]==0||a[l]==1) t[p].flag=1; else t[p].flag=0; return ; } int mid=l+r>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); updata(p); } void change(int p,int l,int r){ if(t[p].l==t[p].r){ t[p].sum=(ll)sqrt(t[p].sum); if(t[p].sum==0||t[p].sum==1) t[p].flag=1; return ; } int mid=t[p].l+t[p].r>>1; if(l<=mid&&!t[p<<1].flag) change(p<<1,l,r); if(r>mid&&!t[p<<1|1].flag) change(p<<1|1,l,r); updata(p); } ll ask(int p,int l,int r){ // cout<<t[p].sum<<endl; if(l<=t[p].l&&t[p].r<=r) return t[p].sum; int mid=t[p].l+t[p].r>>1; ll ans=0; if(l<=mid) ans+=ask(p<<1,l,r); if(r>mid) ans+=ask(p<<1|1,l,r); return ans; } int main(){ // freopen("out.docx","w",stdout); int x,y,opt; n=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); qnum=read(); for(int i=1;i<=qnum;i++){ opt=read();x=read();y=read(); if(opt==1) printf("%lld ",ask(1,x,y)); else change(1,x,y); }return 0; }
时间复杂度上来说，每个数最多被开大约5次（可以自己拿计算机按按），那么每个区间最多拜访的次数也不会太大，所以均摊一下，过掉这道题是没什么问题的。