SP1716 GSS3 - Can you answer these queries III(区间最大子段和+单点修改)

你的名字 2021-11-11 14:50 144阅读 0赞

# 题意 #

给出n个数，q次操作，两种操作：把ax改成y，求\[l,r\]的最大子段和。

n,m<=50000,-10000<=ai<=10000

# 题解 #

区间问题想到用线段树维护，考虑如何合并区间。

当我们求出两段小区间的最大子段和，那么大区间的最大子段和可能是这两个的其中一个，也可能是中间两个区间拼接的部分，这部分就是左区间右边最大的部分和右区间左边最大的部分组成。

所以我们还需要记录区间紧靠左边和紧靠右边的最大子段和，现在考虑维护左边的最大子段和lmax，在区间合并时，大区间的lmax可能是左区间的lmax，也可能是左边整个区间加上右边区间的lmax。rmax同理。

区间查询的时候传结构体才能合并信息。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    using namespace std;
    
    #define ls rt<<1
    #define rs rt<<1|1
    #define ll long long
    const int maxn=50005;
    int n,m;
    int a[maxn];
    struct cx{
      ll sum,dat,lmax,rmax;// 区间和,区间最大子段和,左端最大子段和,右端最大子段和
    }t[maxn<<2];
    
    ll max(ll x,ll y){
          return x>y ? x : y ;}
    
    void get(cx &ret,cx lx,cx ry){
      ret.sum=lx.sum+ry.sum;
      ret.lmax=max(lx.lmax,lx.sum+ry.lmax);
      ret.rmax=max(ry.rmax,ry.sum+lx.rmax);
      ret.dat=max(max(lx.dat,ry.dat),lx.rmax+ry.lmax);
    }
    
    void build(int rt,int l,int r){
      if(l==r){
        t[rt]=(cx){a[l],a[l],a[l],a[l]};
        return ;
      }
      int mid=(l+r)>>1;
      build(ls,l,mid);
      build(rs,mid+1,r);
      get(t[rt],t[ls],t[rs]);
    }
    
    cx query(int rt,int l,int r,int a_l,int a_r){
      //printf("%d %d %d %d \n",l,r,a_l,a_r);
      if(a_l<=l&&r<=a_r) return t[rt];
      int mid=(l+r)>>1;
      if(a_r<=mid) return query(ls,l,mid,a_l,a_r);
      if(mid<a_l) return query(rs,mid+1,r,a_l,a_r);
      cx ret,x,y;
      x=query(ls,l,mid,a_l,a_r);
      y=query(rs,mid+1,r,a_l,a_r);
      get(ret,x,y);
      return ret;
    }
    
    void modify(int rt,int l,int r,int pos,int val){
      if(l==r){
        t[rt]=(cx){val,val,val,val};
        return ;
      }
      int mid=(l+r)>>1;
      if(pos<=mid) modify(ls,l,mid,pos,val);
      else modify(rs,mid+1,r,pos,val);
      get(t[rt],t[ls],t[rs]);
    }
    
    int main(){
      scanf("%d",&n);
      for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      build(1,1,n);
      scanf("%d",&m);
      for(int i=1;i<=m;i++){
        int opt;
        scanf("%d",&opt);
        if(opt){
          int l,r;
          scanf("%d%d",&l,&r);
          printf("%lld\n",query(1,1,n,l,r).dat);
        }
        else {
          int pos,val;
          scanf("%d%d",&pos,&val);
          modify(1,1,n,pos,val);
        }
      }
    }

转载于:https://www.cnblogs.com/sto324/p/11297438.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/f595cfa35a314b8783ab95aaaa963fa7.png