[POI2015]KIN

题目

感觉这种题好套路啊，怎么又是这个做法

癌不过怎么没有人和我一样些写套路做法，那干脆来写个题解吧

我们考虑枚举区间的右端点，这样我们只需要考虑从\(1\)到\(i\)的最大区间就好了

由于我们选择了这个位置作为区间的右端点，首先产生的贡献是这个电影的价值，但我们上一次看得这个电影就不能产生贡献了，而且不仅仅是不能产生贡献了，还得把原来的贡献减掉，于是把原来的位置取反

相应的，上上次出现的位置我们取反了，这次就不用考虑它了，于是把那个位置变成\(0\)就好了

最后的答案就是最大子段和了，线段树随便维护一下就好了

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define LL long long

#define re register

#define maxn 1200005

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int n,m;

int l[maxn<<1],r[maxn<<1];

LL d[maxn<<1],lc[maxn<<1],rc[maxn<<1],ans,sum[maxn<<1];

int nx[maxn],cnt[maxn];

int w[maxn],a[maxn],pos[maxn];

inline void pushup(int i) {

	sum[i]=sum[i<<1|1]+sum[i<<1];

	lc[i]=max(lc[i<<1],sum[i<<1]+lc[i<<1|1]);

	rc[i]=max(rc[i<<1|1],sum[i<<1|1]+rc[i<<1]);

	d[i]=max(d[i<<1],d[i<<1|1]);d[i]=max(d[i],lc[i<<1|1]+rc[i<<1]);

}

void build(int x,int y,int i) {

	l[i]=x,r[i]=y;

	if(x==y) return;

	int mid=x+y>>1;

	build(x,mid,i<<1),build(mid+1,y,i<<1|1);

}

void change(int pos,int i,int val) {

	if(pos==l[i]&&l[i]==r[i]) {d[i]=sum[i]=lc[i]=rc[i]=val;return;}

	int mid=l[i]+r[i]>>1;

	if(pos<=mid) change(pos,i<<1,val);

		else change(pos,i<<1|1,val);

	pushup(i);

}

int main() {

	n=read(),m=read();

	for(re int i=1;i<=n;i++) a[i]=read();

	for(re int i=1;i<=m;i++) w[i]=read();

	build(1,n,1);

	for(re int i=1;i<=n;i++)

		nx[i]=pos[a[i]],pos[a[i]]=i;

	for(re int i=1;i<=n;i++) {

		if(!nx[i]) change(i,1,w[a[i]]);

			else if(!nx[nx[i]]) change(i,1,w[a[i]]),change(nx[i],1,-1*w[a[i]]);

				else change(i,1,w[a[i]]),change(nx[i],1,-1*w[a[i]]),change(nx[nx[i]],1,0);

		ans=max(ans,d[1]);

	}

	printf("%lld\n",ans);

	return 0;

}