问题描述
共有m部电影，编号为1m，第i部电影的好看值为w[i]。在n天之中（从1n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
输入格式
第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],f[2],…,f[n] (1<=f[i]<=m)。第三行包含m个整数w[1],w[2],…,w[m] (1<=w[j]<=1000000)。
输出格式
输出观看且仅观看过一次的电影的好看值的总和的最大值。
样例输入
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
样例输出
15
说明
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
解析
如果不计重复的话，这道题就是求最大子段和的问题。但是，现在牵涉到重复的不能计入贡献的问题。我们可以选择在每次遇到一个前面出现过的元素，就把前面那个相同的贡献改为-1。不妨记前面与i种类相同的元素位置为(pre[i])，如果(pre[i])之前还有与它相同的，就把(pre[i])前面的贡献改为0。所以，我们需要用线段树维护最大子段和，支持动态修改贡献。
这样做的问题在于修改后前面统计的答案是错误的。因此，我们可以在每次修改贡献之前都更新一次答案，这样就避免了这种问题。
代码
#include <iostream>
#include <cstdio>
#define int long long
#define N 1000002
using namespace std;
struct SegmentTree{
int dat,sum,l,r;
}t[N*4];
int n,m,i,a[N],w[N],pre[N],last[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void update(int p)
{
t[p].sum=t[p*2].sum+t[p*2+1].sum;
t[p].l=max(t[p*2].l,t[p*2].sum+t[p*2+1].l);
t[p].r=max(t[p*2+1].r,t[p*2+1].sum+t[p*2].r);
t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].r+t[p*2+1].l);
}
void change(int p,int l,int r,int x,int val)
{
if(l==r){
t[p].dat=t[p].sum=t[p].l=t[p].r=val;
return;
}
int mid=(l+r)/2;
if(x<=mid) change(p*2,l,mid,x,val);
else change(p*2+1,mid+1,r,x,val);
update(p);
}
signed main()
{
n=read();m=read();
for(i=1;i<=n;i++) a[i]=read();
for(i=1;i<=m;i++) w[i]=read();
int ans=0;
for(i=1;i<=n;i++){
pre[i]=last[a[i]];
last[a[i]]=i;
if(pre[i]) change(1,1,n,pre[i],-w[a[i]]);
if(pre[pre[i]]) change(1,1,n,pre[pre[i]],0);
change(1,1,n,i,w[a[i]]);
ans=max(ans,t[1].dat);
}
printf("%lld
",ans);
return 0;
}