另一个画风的GSS1 - Can you answer these queries I（猫树）-白红宇

另一个画风的GSS1 - Can you answer these queries I（猫树）

阅读量：7227 次

发布时间：2019-06-29

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

前言

其实我觉得你看猫锟的解释也看不懂（~~主要是还有一些不良心的讲解者不讲清楚~~，当然这里不是针对了qwq）

Solution

考虑我们的线段树是个啥玩意？

每一层都是一堆区间叠在一起。

我们在每一个节点维护的又是什么？

左边的max，右边的max，中间的max，还有sum。

那么我们改变一下：

令\(p_{dps,i}\)表示在深度为\(dps\)的线段树上\(i\)这个节点所在区间的左边的max，右边的max，然后就可以在\(build\)的时候求

再令\(p_{dps,i}\)表示在深度为\(dps\)的线段树上\(i\)这个节点所在区间的到中间的\(max\)，然后也可以在\(build\)的时候求。

然后就可以\(\Theta(1)\)的询问就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=500010;int pos[N],p[21][N],s[21][N],a[N],Log2[N<<3],n;void build(int o,int l,int r,int dps){ if(l==r) { pos[l]=o; return; } int mid=(l+r)>>1,pre,sm; p[dps][mid]=s[dps][mid]=sm=pre=a[mid]; if(sm<0)sm=0; for(int i=mid-1;i>=l;i--) { sm+=a[i];pre+=a[i]; s[dps][i]=max(s[dps][i+1],pre); p[dps][i]=max(p[dps][i+1],sm); if(sm<0)sm=0; } p[dps][mid+1]=s[dps][mid+1]=sm=pre=a[mid+1]; if(sm<0)sm=0; for(int i=mid+2;i<=r;i++) { sm+=a[i];pre+=a[i]; s[dps][i]=max(s[dps][i-1],pre); p[dps][i]=max(p[dps][i-1],sm); if(sm<0)sm=0; } build(o<<1,l,mid,dps+1); build(o<<1|1,mid+1,r,dps+1);}int query(int l,int r){ if(l==r)return a[l]; int dps=Log2[pos[l]]-Log2[pos[l]^pos[r]]; return max(max(p[dps][l],p[dps][r]),s[dps][l]+s[dps][r]);}int main(){ n=gi(); for(int i=1;i<=n;i++)a[i]=gi(); int L=2; while(L
             
              <<=1; for(int i=2;i<=L<<1;i++)Log2[i]=Log2[i>>1]+1; build(1,1,L,1); int m=gi(); while(m--) { int l=gi(),r=gi(); printf("%d\n",query(l,r)); } return 0;}

转载于:https://www.cnblogs.com/mle-world/p/10268053.html

你可能感兴趣的文章

九曲黄河万里沙,浪淘风簸自天涯 — 正则表达式