1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 #define lson rt<<1,l,m 6 #define rson rt<<1|1,m+1,r 7 int Num,CH[12],f,c; 8 inline void R(int &x){ 9     c=0;f=1;10     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1;11     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘);12     x*=f;13 }14 typedef long long ll;15 int n,m,w[1000001],now[1000001],b[1000001],fa[1000001];16 ll ans,maxv[4000001],delta[4000001];17 void pushdown(int rt)18 {19     if(delta[rt])20       {21         delta[rt<<1]+=delta[rt]; delta[rt<<1|1]+=delta[rt];22         maxv[rt<<1]+=delta[rt]; maxv[rt<<1|1]+=delta[rt];23         delta[rt]=0;24       }25 }26 void update(int ql,int qr,int v,int rt,int l,int r)27 {28     if(ql<=l&&r<=qr)29       {30         delta[rt]+=(ll)v;31         maxv[rt]+=(ll)v;32         return;33       }34     pushdown(rt); int m=l+r>>1;35     if(ql<=m) update(ql,qr,v,lson);36     if(m<qr) update(ql,qr,v,rson);37     maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);38 }39 ll query(int qr,int rt,int l,int r)40 {41     if(1<=l&&r<=qr) return maxv[rt];42     pushdown(rt);43     int m=l+r>>1; ll res=0;44     if(1<=m) res=max(res,query(qr,lson));45     if(m<qr) res=max(res,query(qr,rson));46     return res;47 }48 int main()49 {50     R(n); R(m);51     for(int i=1;i<=n;++i) R(b[i]);52     for(int i=1;i<=m;++i) R(w[i]);53     for(int i=1;i<=n;++i)54       {55           fa[i]=now[b[i]];56           now[b[i]]=i;57       }58     for(int i=1;i<=n;++i)59       {60           update(fa[i]+1,i,(ll)w[b[i]],1,1,n);61           if(fa[i]) update(fa[fa[i]]+1,fa[i],(ll)(-w[b[i]]),1,1,n);62           ans=max(ans,query(i,1,1,n));63       } printf("%lld\n",ans);64     return 0;65 }