【题解】
扫描线+线段树。
我们记第i部电影上次出现的位置是$pre[i]$，我们从$1$到$n$扫描，每次区间$(pre[i],i]$加上第i部电影的贡献$w[f[i]]$，区间$[pre[pre[i]],pre[i]]$减去第i部电影的贡献$w[f[i]]$.
1 #include2 #include 3 #define N 1000010 4 #define rg register 5 #define ls (u<<1) 6 #define rs (u<<1|1) 7 #define mid ((l+r)>>1) 8 #define LL long long 9 using namespace std;10 int n,m,f[N],w[N],pos[N],pre[N];11 LL ans;12 struct tree{13 LL mx,del;14 }a[N<<2];15 inline int read(){16 int k=0,f=1; char c=getchar();17 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();18 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();19 return k*f;20 }21 inline LL max(LL x,LL y){22 return x>y?x:y;23 }24 inline void pushup(int u){25 a[u].mx=max(a[ls].mx,a[rs].mx);26 }27 inline void pushdown(int u){28 if(!a[u].del) return;29 LL d=a[u].del; a[u].del=0;30 a[ls].mx+=d; a[ls].del+=d;31 a[rs].mx+=d; a[rs].del+=d;32 }33 void add(int u,int ql,int qr,int l,int r,LL d){34 //printf("%d %d %d %d\n",ql,qr,l,r); 35 if(ql<=l&&r<=qr){36 a[u].del+=d; a[u].mx+=d; return;37 }38 pushdown(u);39 if(ql<=mid) add(ls,ql,qr,l,mid,d);40 if(qr>mid) add(rs,ql,qr,mid+1,r,d);41 pushup(u);42 }43 int main(){44 n=read(); m=read();45 for(int i=1;i<=n;i++){46 f[i]=read();47 pre[i]=pos[f[i]]; pos[f[i]]=i;48 }49 for(int i=1;i<=m;i++) w[i]=read();50 for(int i=1;i<=n;i++){51 int prefix=pre[i];52 add(1,prefix+1,i,1,n,w[f[i]]);53 if(prefix) add(1,pre[prefix]+1,prefix,1,n,-w[f[i]]);54 ans=max(ans,a[1].mx);55 }56 printf("%lld\n",ans);57 return 0;58 }