自动搬运

查看原文

来自洛谷，原作者为

	_ctz Ádigie šos ök iroг.

搬运于2025-08-24 21:50:25，当前版本为作者最后更新于2019-03-05 14:03:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

安利一波我的$blog$

传送门

这篇题解的思路其实是因机房某位王姓神仙指点而来$QwQ$

首先要会线段树维护最大子段和，不会的可以做做这个

把题目简化一下：

任取一段闭区间，使区间贡献最大

有没有种最大子段和的感觉？但是要求数字重复的不能算。那么如果有两个相同的元素，一个贡献置为为正，另一个置为负，互相抵消就能去重了。于是扫一遍依次加入每个点的贡献，每次都取一下当前最大值。

放个图来看：

红色的是相同的元素。

在第一个红点会有正的贡献$a$。

然后加到第二个：

把第一个置为$-a$，这时如果同时选$1$、$2​$点就会正好抵消。而如果只选中第一个点虽然贡献不正确，但是因为是一边扫一遍取最大值，所以这种情况在之前已经被取到了。

再来第三个：

注意要把第一个清零，否则这时如果三个点都选的话贡献就为负了。

记录一下每种颜色上一个出现的位置就能做了$QwQ$。

细节：注意判断该颜色是否为第一次出现。还有要开$long\ long$

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 1000005
#define inf 0x3f3f3f3f
#define pn putchar('\n')
#define px(x) putchar(x)
#define ps putchar(' ')
#define pd puts("======================")
#define pj puts("++++++++++++++++++++++")

using namespace std;

inline int read(){
	int x=0,y=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return y?-x:x;
}
template<typename T>
inline T read(){
	T x=0;
	int y=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return y?-x:x;
}
int f[maxn],pre[maxn],last[maxn];
//f是电影，pre[i]是上一个和f[i]相同的位置，last是某种颜色最后一次出现的位置
long long a[maxn];
//a记录电影贡献
struct Segment_Tree{
	long long ll[maxn<<2],rr[maxn<<2],ma[maxn<<2],sum[maxn<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
	inline void update(int node){
		sum[node]=sum[ls(node)]+sum[rs(node)];
		ll[node]=max(ll[ls(node)],sum[ls(node)]+ll[rs(node)]);
		rr[node]=max(rr[rs(node)],sum[rs(node)]+rr[ls(node)]);
		ma[node]=max(max(ma[ls(node)],ma[rs(node)]),rr[ls(node)]+ll[rs(node)]);
	}
	void add(int poi,int l,int r,int node,long long d){
        //把点poi的值改为d
		if(l==r){
			sum[node]=ll[node]=rr[node]=ma[node]=d;
			return;
		}
		int mid=l+r>>1;
		if(poi<=mid)add(poi,l,mid,ls(node),d);
		else add(poi,mid+1,r,rs(node),d);
		update(node);
	}
}st;
int main(){
	int n=read(),m=read();
	for(register int i=1;i<=n;++i)
		f[i]=read();
	for(register int i=1;i<=m;++i)
		a[i]=read<long long>();
	long long ans=0;
	for(register int i=1;i<=n;++i){
		pre[i]=last[f[i]],last[f[i]]=i;
		if(pre[i])st.add(pre[i],1,n,1,-a[f[i]]);
        //把上一个该颜色的位置贡献置为负
		if(pre[pre[i]])st.add(pre[pre[i]],1,n,1,0);
        //把上上个贡献置为0
		st.add(i,1,n,1,a[f[i]]);
        //加上该点的贡献
		ans=max(ans,st.ma[1]);
        //一边跑一边取最大值
	}
	printf("%lld\n",ans);
}