【luogu4145】 上帝造题的七分钟2 / 花神游历各国 [线段树]
把一段区间里的每个数都开方 求区间和
可以发现最多开方开6次就能都变为1 所以可以hei暴力地一个点一个点地改 具体操作我用的和buildtree差不多
还要注意 是当前区间的最大值<=1时才不处理 我写的==1QAQ 导致BZOJ上有一个点超时
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; #define ll long long #define rg register #define lson o<<1 #define rson o<<1|1 const int N=100000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827; int n,m; ll a[N],sum[N<<2],mx[N<<2]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } void pushup(int o){ sum[o]=sum[lson]+sum[rson]; mx[o]=max(mx[lson],mx[rson]); } void update(int o,int l,int r,int x,int y){ if(r<x||y<l) return; if(x<=l&&r<=y&&mx[o]<=1) return; if(l==r) {sum[o]=mx[o]=floor(sqrt(mx[o]));return;} int mid=(l+r)>>1; update(lson,l,mid,x,y),update(rson,mid+1,r,x,y); pushup(o); } void buildtree(int o,int l,int r){ if(l==r) {sum[o]=mx[o]=a[l];return;} int mid=(l+r)>>1; buildtree(lson,l,mid); buildtree(rson,mid+1,r); pushup(o); } ll query(int o,int l,int r,int x,int y){ ll ans=0; if(r<x||y<l) return 0; if(x<=l&&r<=y) return sum[o]; int mid=(l+r)>>1; ans+=query(lson,l,mid,x,y); ans+=query(rson,mid+1,r,x,y); return ans; } int main(){ rd(n); for(int i=1;i<=n;++i) rd(a[i]); buildtree(1,1,n); rd(m); while(m--){ int k,l,r; rd(k),rd(l),rd(r); if(l>r) swap(l,r); if(k==2) update(1,1,n,l,r); else printf("%lld ",query(1,1,n,l,r)); } return 0; }