线段树经典运用。
设$last_i$表示上一个与$i$相同的类型。然后每次更新$[last[i]+1,i]$和$[last[last[i]]+1,last[i]]$的答案就行了。
//BZOJ 3747 //by Cydiater //2016.10.28 #include <iostream> #include <queue> #include <map> #include <ctime> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <cstdio> #include <cstdlib> #include <bitset> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) const int MAXN=1e6+5; const int oo=0x3f3f3f3f; inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int N,M,typ[MAXN],hap[MAXN],last[MAXN],newpos[MAXN],L,R; ll v,ans=0; struct Tree{ ll delta,v; }t[MAXN<<2]; namespace solution{ inline void reload(int root){t[root].v=max(t[root<<1].v,t[root<<1|1].v);} void init(){ N=read();M=read(); up(i,1,N){ typ[i]=read(); last[i]=newpos[typ[i]]; newpos[typ[i]]=i; } up(i,1,M)hap[i]=read(); } void downit(int root){ if(t[root].delta==0) return; ll delta=t[root].delta;t[root].delta=0; t[root<<1].delta+=delta;t[root<<1|1].delta+=delta; t[root<<1].v+=delta;t[root<<1|1].v+=delta; } void updata(int leftt,int rightt,int root){ if(leftt!=rightt)downit(root); if(leftt>R||rightt<L) return; if(leftt>=L&&rightt<=R){ t[root].delta=v; t[root].v+=v; return; } int mid=(leftt+rightt)>>1; updata(leftt,mid,root<<1); updata(mid+1,rightt,root<<1|1); reload(root); } void slove(){ up(i,1,N){ L=last[i]+1;R=i;v=hap[typ[i]]; updata(1,N,1); if(last[i]!=0){ L=last[last[i]]+1;R=last[i];v=-hap[typ[i]]; updata(1,N,1); } cmax(ans,t[1].v); } cout<<ans<<endl; } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); return 0; }