SP2713 GSS4 - Can you answer these queries IV

妖狐艹你老母 2021-09-29 14:58 176阅读 0赞

[**传送门**][Link 1]

--------------------

\\(ZHX\\; TQL\\) Orz

--------------------

这道题目我们可以用线段树维护……

可能有\\(dalao\\)会问：“线段树怎么维护区间开平方？”

而这道题的精髓就在于，它要我们维护的操作是**开平方+下取整**。也就是说经过一定的次数，要开平方的数会慢慢缩小为"\\(1\\)"，这个次数是很小的，而\\(\\sqrt 1=1\\)。

所以在修改时，我们可以先查询这个区间是否全是"1"，如果是，那我们就不管它，再去寻找其他的区间进行修改，如果这个区间里有其他数，我们就将这些递归寻找这些数，然后单点修改进行开平方操作。

\\(\\tt\{P.S.\}\\) 要注意这个题目的输出格式

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define mid ((l+r)>>1) #define LL long long #define ls p<<1 #define rs p<<1|1 using namespace std; LL tree[100010<<4],a[100010]; inline void up(int p){ tree[p]=tree[ls]+tree[rs]; } void build(int l,int r,int p){ if(l==r){ tree[p]=a[l]; return ; } build(l,mid,ls); build(mid+1,r,rs); up(p); } void update(int l,int r,int p,int nl,int nr){ if(l>=nl&&r<=nr){ if(tree[p]<=r-l+1) return ; else{ if(l==r){ tree[p]=(int)sqrt((double)tree[p]); return ; } } } up(p); if(nl<=mid) update(l,mid,ls,nl,nr); up(p); if(nr>mid) update(mid+1,r,rs,nl,nr); up(p); } LL query(int l,int r,int p,int nl,int nr){ LL ans=0; if(l>=nl&&r<=nr) return tree[p]; if(nl<=mid) ans+=query(l,mid,ls,nl,nr); if(nr>mid) ans+=query(mid+1,r,rs,nl,nr); return ans; } LL read(){ LL k=0,f=1; char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c<='9';c=getchar()) k=k*10+c-48; return k*f; } int main(){ //freopen("hh.in","r",stdin); //freopen("hh.out","w",stdout); int n,tot=0; while(scanf("%d\n",&n)!=EOF){ printf("Case #%d:\n",++tot); for(int i=1;i<=n;i++) a[i]=read(); build(1,n,1); int m=read(); for(int i=1;i<=m;i++){ int k=read(),l=read(),r=read(); if(l>r) swap(l,r); if(k==0) update(1,n,1,l,r); else printf("%lld\n",query(1,n,1,l,r)); } printf("\n"); } return 0; }

转载于:https://www.cnblogs.com/wxl-Ezio/p/9593582.html

[Link 1]: https://www.spoj.com/problems/GSS4/