这篇题解的思路其实是因机房某位王姓神仙指点而来$QwQ$
首先要会线段树维护最大子段和，不会的可以做做这个
把题目简化一下：
任取一段闭区间，使区间贡献最大
有没有种最大子段和的感觉？但是要求数字重复的不能算。那么如果有两个相同的元素，一个贡献置为正，另一个置为负，互相抵消就能去重了。于是扫一遍依次加入每个点的贡献，每次都取一下当前最大值。
放个图来看：
红色的是相同的元素。
在第一个红点会有正的贡献$a$。
然后加到第二个：
把第一个置为$-a$，这时如果同时选$1$、$2$点就会正好抵消。而如果只选中第一个点虽然贡献不正确，但是因为是一边扫一遍取最大值，所以这种情况在之前已经被取到了。
再来第三个：
注意要把第一个清零，否则这时如果三个点都选的话贡献就为负了。
记录一下每种颜色上一个出现的位置就能做了$QwQ$。
细节：注意判断该颜色是否为第一次出现。还有要开$long\ long$
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 1000005
#define inf 0x3f3f3f3f
#define pn putchar('\n')
#define px(x) putchar(x)
#define ps putchar(' ')
#define pd puts("======================")
#define pj puts("++++++++++++++++++++++")
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int f[maxn],pre[maxn],last[maxn];
//f是电影，pre[i]是上一个和f[i]相同的位置，last是某种颜色最后一次出现的位置
long long a[maxn];
//a记录电影贡献
struct Segment_Tree{
long long ll[maxn<<2],rr[maxn<<2],ma[maxn<<2],sum[maxn<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
inline void update(int node){
sum[node]=sum[ls(node)]+sum[rs(node)];
ll[node]=max(ll[ls(node)],sum[ls(node)]+ll[rs(node)]);
rr[node]=max(rr[rs(node)],sum[rs(node)]+rr[ls(node)]);
ma[node]=max(max(ma[ls(node)],ma[rs(node)]),rr[ls(node)]+ll[rs(node)]);
}
void add(int poi,int l,int r,int node,long long d){
//把点poi的值改为d
if(l==r){
sum[node]=ll[node]=rr[node]=ma[node]=d;
return;
}
int mid=l+r>>1;
if(poi<=mid)add(poi,l,mid,ls(node),d);
else add(poi,mid+1,r,rs(node),d);
update(node);
}
}st;
int main(){
int n=read(),m=read();
for(register int i=1;i<=n;++i)
f[i]=read();
for(register int i=1;i<=m;++i)
a[i]=read<long long>();
long long ans=0;
for(register int i=1;i<=n;++i){
pre[i]=last[f[i]],last[f[i]]=i;
if(pre[i])st.add(pre[i],1,n,1,-a[f[i]]);
//把上一个该颜色的位置贡献置为负
if(pre[pre[i]])st.add(pre[pre[i]],1,n,1,0);
//把上上个贡献置为0
st.add(i,1,n,1,a[f[i]]);
//加上该点的贡献
ans=max(ans,st.ma[1]);
//一边跑一边取最大值
}
printf("%lld\n",ans);
}
