考虑固定左端点，求出该情况下能获得的最大值。于是每次可以在某数第一次出现的位置加上其价值，第二次出现的位置减掉其价值，查询前缀最大值就可以了。每次移动左端点在线段树上更新即可。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 1000010#define ll long longint n,m,a[N],b[N],p[N],nxt[N];int L[N<<2],R[N<<2];ll mx[N<<2],sum[N<<2],ans;void build(int k,int l,int r){ L[k]=l,R[k]=r; if (l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);}void up(int k){ sum[k]=sum[k<<1]+sum[k<<1|1]; mx[k]=max(mx[k<<1],sum[k<<1]+mx[k<<1|1]);}void modify(int k,int p,int x){ if (L[k]==R[k]) {mx[k]=sum[k]=x;return;} int mid=L[k]+R[k]>>1; if (p<=mid) modify(k<<1,p,x); else modify(k<<1|1,p,x); up(k);}ll query(int k,int l,int r){ if (L[k]==l&&R[k]==r) return mx[k]; int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return max(query(k<<1,l,mid),sum[k<<1]+query(k<<1|1,mid+1,r));}int main(){#ifndef ONLINE_JUDGE freopen("bzoj3747.in","r",stdin); freopen("bzoj3747.out","w",stdout); const char LL[]="I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(); for (int i=1;i<=n;i++) { a[i]=read(); nxt[p[a[i]]]=i,p[a[i]]=i; } for (int i=1;i<=n;i++) if (!nxt[i]) nxt[i]=n+1;nxt[n+1]=n+1; for (int i=1;i<=m;i++) b[i]=read(); build(1,1,n+1); memset(p,0,sizeof(p)); for (int i=1;i<=n;i++) if (!p[a[i]]) p[a[i]]=1,modify(1,i,b[a[i]]),modify(1,nxt[i],-b[a[i]]); for (int i=1;i<=n;i++) { ans=max(ans,query(1,i,n)); modify(1,i,0),modify(1,nxt[i],b[a[i]]),modify(1,nxt[nxt[i]],-b[a[i]]); } cout<