线段树
开根号好像没办法搞延迟标记
但是可以发现 10^12 只要开 6 次根号向下取整就等于 1
1再怎么开也是1
所以一个数最多只要开6次根号就不用再搞了
我们可以维护一个最大值
如果整个区间的最大值<=1
那么整个区间都不需要修改，直接跳过就好了
不然的话就暴力开根
修改复杂度 O(6nlogn)
询问复杂度 O(logn)
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; int n,m; ll a[N]; ll t[N],mx[N]; int cnt[N]; inline void pushup(int &o)//用儿子更新o节点 { t[o]=t[o<<1]+t[o<<1|1]; mx[o]=max(mx[o<<1],mx[o<<1|1]); } void build(int l,int r,int o)//建树 { if(l==r) { t[o]=mx[o]=a[l]; return; } int mid=(l+r)>>1; build(l,mid,o<<1); build(mid+1,r,o<<1|1); pushup(o); } void change(int l,int r,int o,ll &ql,ll &qr)//暴力修改 { if(r<ql||l>qr) return; if(l==r) { if(mx[o]>1) { t[o]=sqrt(t[o]); mx[o]=sqrt(mx[o]); } return; } int mid=(l+r)>>1; if(mx[o<<1]>1) change(l,mid,o<<1,ql,qr);//如果区间最大值<=1就不要修改了 if(mx[o<<1|1]>1) change(mid+1,r,o<<1|1,ql,qr); pushup(o); } ll query(int l,int r,int o,ll &ql,ll &qr)//普通的询问 { if(r<ql||l>qr) return 0; if(l>=ql&&r<=qr) return t[o]; int mid=(l+r)>>1; return query(l,mid,o<<1,ql,qr)+query(mid+1,r,o<<1|1,ql,qr); } int main() { cin>>n; for(int i=1;i<=n;i++) a[i]=read(); build(1,n,1); ll k,l,r; cin>>m; while(m--) { k=read(); l=read(); r=read(); if(l>r) swap(l,r);//坑点，如果l>r就交换l,r if(k) printf("%lld ",query(1,n,1,l,r)); else change(1,n,1,l,r); } return 0; }