Luogu

分析

首先这个东西长得和最大子段和很类似,于是我们先把 GSS3 的代码蒯过来

考虑怎么让它变成最大子段和。为了方便,设 $pre_i$ 表示上一个和 $i$ 电影相同的。

我们从左往右扫,假设现在扫到了 $i$,那么在线段树中把 $i$ 位置赋值为 $w_{f_i}$,把 $pre_i$ 位置赋值为 $-w_{f_i}$,把 $pre_{pre_i}$ 位置赋值为 $0$。

这样为什么是对的呢?最大子段如果只包含了 $i$,那么没有什么影响;如果同时包含了 $pre_i$ 和 $i$,那么贡献抵消掉了,也没有影响;如果只包含了 $pre_i$,那么这个之前就算过了,所以还是没有什么影响。

然后 $pre_{pre_i}$ 赋值为 $0$ 是因为后面两个已经抵消了,所以 $pre_{pre_i}$ 要赋值为 $0$ 避免多减一些东西。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,m,f[N],w[N];
int pre[N],lst[N];

struct node { int sum,lmax,rmax,ans; };
node operator +(node a,node b) {
    node c;
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax);
    return c;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[N<<2];
inline void modify(int o,int l,int r,int p,int w) {
    if (l==r) {
        t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=w;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    t[o]=t[ls]+t[rs];
}
#undef ls
#undef rs

signed main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) f[i]=read();
    for (re int i=1;i<=m;++i) w[i]=read();
    int ans=0;
    for (re int i=1;i<=n;++i) {
        pre[i]=lst[f[i]],lst[f[i]]=i;
        modify(1,1,n,i,w[f[i]]);
        if (pre[i]) modify(1,1,n,pre[i],-w[f[i]]);
        if (pre[pre[i]]) modify(1,1,n,pre[pre[i]],0);
        ans=max(ans,t[1].ans);
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 10 月 18 日 10 : 27 PM