Bzoj3211花神游历各国-白红宇

Bzoj3211花神游历各国

阅读量：5153 次

发布时间：2019-06-13

本文共 3116 字，大约阅读时间需要 10 分钟。

提供一种数据结构，支持区间求和，以及区间开根号。

这种题一般暴力谁都能打，主要是练线段树。

下面给出两种解法：

第一种，额外维护区间最大值。

由于1、0开根是其本身，开根没有意义，我们维护区间最大值，如果区间最大值已经为1或0则直接return，否则继续向下开根。

剩下的维护区间和就可以了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #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\n",ask(1,y,z)); else change(1,y,z); }return 0;}

View Code

第二种，维护lazy，表示是否已经全是1或0。

如果是，则直接return，否则继续向下开根。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #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<
             
              <
              
               >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\n",ask(1,x,y)); else change(1,x,y); }return 0;}

View Code

时间复杂度上来说，每个数最多被开大约5次（可以自己拿计算机按按），那么每个区间最多拜访的次数也不会太大，所以均摊一下，过掉这道题是没什么问题的。

转载于:https://www.cnblogs.com/Yu-shi/p/11138129.html

你可能感兴趣的文章