upc 最⼤⼦段和线段树 + 懒标-白红宇的个人博客

upc 最⼤⼦段和线段树 + 懒标

发布日期：2021-09-25 23:57:48 浏览次数：6 分类：技术文章

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

最⼤⼦段和

时间限制: 1 Sec 内存限制: 128 MB

题目描述

现在给你⼀个序列a1…an,求⼀个权值和最⼤的区间（区间可以为空），其中相同的数只算⼀次。

输入

第⼀⾏⼀个正整数n,

接下来⼀⾏n个整数，a1到an。

输出

⼀⾏⼀个整数表⽰答案。

样例输入 Copy

【样例1】

1 -3 2 2 -4

【样例2】

4 -2 0 -2 3

样例输出 Copy

【样例1】

【样例2】

提示

对于100%的数据，n≤200000，|ai|≤108

师傅巨巨给的思路，orz。

考虑用线段树维护一段连续区间，假设这个连续区间用 b [ j ] 表示，b [ j ] 表示 a [ j ] ~ a [ i ] 的连续区间，i 是当前枚举到的数，从 1 ~ n 枚举，也就是说线段树维护的是一段区间，并不是位置。

枚举的时候分以下两种情况

(1)当前 a [ i ] 在之前没有出现过的时候，那么直接将 1 ~ i 用线段树存的区间结尾都加上 a [ i ] ，并更新 a [ i ] 出现的位置。

(2)当前 a [ i ] 在之前 pos 这个位置出现过，那么 pos + 1 ~ i 加上 a [ i ]，并更新位置，也就是 b [ pos + 1 ] ~ b [ i ] 的区间都加 a [ i ] 。

让后线段树每个结点需要存 sum ,lazy ,msum ,mlazy，sum是存的当前区间的和，msum存的是当前区间最大子段和，lazy是懒标，mlazy是懒标的最大子段和。

除了pushdown操作其他的都很简单，跟普通的线段树一样，讲一下pushdown。

(1)更新 msum 的时候，儿子的 sum + 父亲的 mlazy ，不用子区间 msum 来更新是因为儿子 msum 不一定能和父亲的 mlazy 接起来。

(2)更新 mlazy 的时候，儿子的 lazy + 父亲的 mlazy ，这个理解方式跟(1)一样，因为lazy也算是一个连续区间，而儿子的 mlazy 不一定能跟父亲的 mlazy 接起来。

(3)对于儿子的 sum 和 lazy ，直接把懒标接在后面即可。

其他的实现具体可以看代码。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=200010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int a[N];map
                
                 mp;struct Node{ int l,r; LL sum,lazy; LL msum,mlazy;}tr[N<<2];void pushup(int u){ tr[u].sum=max(tr[L].sum,tr[R].sum);//因为sum存的是区间和，两个区间应该取max，而非相加。 tr[u].msum=max(tr[L].msum,tr[R].msum);}void pushdown(int u){ if(tr[u].lazy==0&&tr[u].mlazy==0) return; LL &lazy=tr[u].lazy,&mlazy=tr[u].mlazy; tr[L].msum=max(tr[L].msum,tr[L].sum+mlazy);//更新最大子段 tr[R].msum=max(tr[R].msum,tr[R].sum+mlazy); tr[L].mlazy=max(tr[L].mlazy,tr[L].lazy+mlazy);//更新懒标的最大子段 tr[R].mlazy=max(tr[R].mlazy,tr[R].lazy+mlazy); tr[L].lazy+=lazy,tr[R].lazy+=lazy;//更新懒标 tr[L].sum+=lazy,tr[R].sum+=lazy;//更新区间和 tr[u].lazy=tr[u].mlazy=0;//清零}void build(int u,int l,int r){ tr[u]={ l,r,0,0,0,0}; if(l==r) return; build(L,l,Mid),build(R,Mid+1,r);}void modify(int u,int l,int r,int c){ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].sum+=c; tr[u].msum=max(tr[u].msum,tr[u].sum); tr[u].lazy+=c; tr[u].mlazy=max(tr[u].mlazy,tr[u].lazy); return; } pushdown(u); if(l<=Mid) modify(L,l,r,c); if(r>Mid) modify(R,l,r,c); pushup(u);}LL query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].msum; pushdown(u); LL ans=0; if(l<=Mid) ans=max(ans,query(L,l,r)); if(r>Mid) ans=max(ans,query(R,l,r)); return ans;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); LL ans=0; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for(int i=1;i<=n;i++) { modify(1,mp[a[i]]+1,i,a[i]); mp[a[i]]=i;//更新位置 ans=max(ans,query(1,1,i)); } printf("%lld\n",ans); return 0;}

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106081948 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：加法线段树 + 思维

下一篇：upc spring 对顶堆 + 贪心

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章