【题意】区间开平方,区间求和
【分析】其实我们没有很好的维护区间开方的数据结构,不过我们可以发现开方的数量级降得很快,手动算一下,大概可以知道每个数至多开方6次,每次暴力去修改的时间复杂度是O(logn)
在实现的过程中,记录一个区间的max,当一个区间的max=1时,操作就没有意义了!
【代码】
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=100000+5; int n,m,k,x,y; struct tree { int l,r; long long val,maxx; }t[maxn*4]; void pushu(int now) { t[now].val=t[now<<1].val+t[now<<1|1].val; t[now].maxx=max(t[now<<1].maxx,t[now<<1|1].maxx); } void build(int now ,int l,int r) { t[now].l=l; t[now].r=r; if(l==r) { scanf("%lld",&t[now].maxx); t[now].val=t[now].maxx; return; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); pushu(now); } void change(int now, int l, int r) { if(t[now].l==t[now].r) { t[now].maxx=sqrt(t[now].maxx); t[now].val=sqrt(t[now].val); return; } int mid=(t[now].l+t[now].r)>>1; if(l<=mid && t[now].maxx>1) change(now<<1,l,r); if(r>mid && t[now].maxx>1) change(now<<1|1,l,r); pushu(now); } long long query(int now, int l ,int r) { if(l<=t[now].l && r>=t[now].r) return t[now].val; int mid=(t[now].l+t[now].r)>>1; long long ans=0; if(l<=mid) ans+=query(now<<1,l,r); if(r>mid) ans+=query(now<<1|1,l,r); return ans; } int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); scanf("%d",&n); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&k,&x,&y); if(x>y) swap(x,y); if(!k) change(1,x,y); else printf("%lld\n",query(1,x,y)); } return 0; }