分析
我们首先要记录一个pre[x]表示上一个颜色和x相同的位置。然后我们枚举所有区间的右端点。我们发现对于每一个新的端点x，会导致pre[pre[x]]+1到pre[x]这一段区间的值减w[col[x]]，导致pre[x]+1到x这一段区间的值加w[col[x]]。所以我们只需要维护这些信息并每次统计[1,x]区间的最大值就可以了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
long long w[1001000],col[1001000],d[4400000],head[1001000];
long long pre[1001000],laz[4400000];
inline void build(long long le,long long ri,long long wh,long long x,long long y,long long k){
if(x>y)return;
if(le>=x&&ri<=y){
d[wh]+=k;
laz[wh]+=k;
return;
}
long long mid=(le+ri)>>1;
if(laz[wh]){
laz[wh<<1]+=laz[wh];
laz[wh<<1|1]+=laz[wh];
d[wh<<1]+=laz[wh];
d[wh<<1|1]+=laz[wh];
laz[wh]=0;
}
if(mid>=x)build(le,mid,wh<<1,x,y,k);
if(mid<y)build(mid+1,ri,wh<<1|1,x,y,k);
d[wh]=max(d[wh<<1],d[wh<<1|1]);
}
inline long long q(long long le,long long ri,long long wh,long long x,long long y){
if(x>y)return 0;
if(le>=x&&ri<=y){
return d[wh];
}
long long mid=(le+ri)>>1,ans=0;
if(laz[wh]){
laz[wh<<1]+=laz[wh];
laz[wh<<1|1]+=laz[wh];
d[wh<<1]+=laz[wh];
d[wh<<1|1]+=laz[wh];
laz[wh]=0;
}
if(mid>=x)ans=max(ans,q(le,mid,wh<<1,x,y));
if(mid<y)ans=max(ans,q(mid+1,ri,wh<<1|1,x,y));
d[wh]=ans;
return ans;
}
int main(){
long long n,m,i,j,k;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)scanf("%lld",&col[i]);
for(i=1;i<=m;i++)scanf("%lld",&w[i]);
for(i=1;i<=n;i++){
pre[i]=head[col[i]];
head[col[i]]=i;
}
long long ans=0;
for(i=1;i<=n;i++){
build(1,n,1,pre[pre[i]]+1,pre[i],-w[col[i]]);
build(1,n,1,pre[i]+1,i,w[col[i]]);
ans=max(ans,q(1,n,1,1,i));
}
printf("%lld
",ans);
return 0;
}