3747: [POI2015]Kinoman

Time Limit: 60 Sec Memory Limit: 128 MB
Submit: 2031 Solved: 840
[Submit][Status][Discuss]

Description
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

Input
第一行两个整数n,m(1<=m<=n<=1000000)。
第二行包含n个整数f[1],f[2],…,fn。
第三行包含m个整数w[1],w[2],…,wm。

Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。

Sample Input
9 4

2 3 1 1 4 1 2 4 1

5 3 6 6

Sample Output
15

样例解释：

观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。

我们枚举每个点作为右端点的时候的答案即可。

然后我们线段树维护当前的点为右端点，每个点分别为左端点的时候的答案，一直更新最大值即可。

我们记录每个点前面一样的出现的位置。然后很容易可以算出来，每个点i加入区间的答案。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m,f[N],pre[N],w[N],vis[N]; ll res;
struct node{int l,r; ll mx,lazy;}t[N<<2];
inline void push_up(int p){t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);}
inline void push_down(int p){
	if(t[p].lazy){
		t[p<<1].lazy+=t[p].lazy,t[p<<1|1].lazy+=t[p].lazy;
		t[p<<1].mx+=t[p].lazy,t[p<<1|1].mx+=t[p].lazy;	t[p].lazy=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r)	return ;	int mid=l+r>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int v){
	if(l>r)	return ;
	if(t[p].l==l&&t[p].r==r){t[p].lazy+=v; t[p].mx+=v; return ;}
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r,v);
	else if(l>mid)	change(p<<1|1,l,r,v);
	else	change(p<<1,l,mid,v),change(p<<1|1,mid+1,r,v);
	push_up(p);
}
signed main(){
	cin>>n>>m;	build(1,1,n);
	for(int i=1;i<=n;i++)	scanf("%d",&f[i]),pre[i]=vis[f[i]],vis[f[i]]=i;
	for(int i=1;i<=m;i++)	scanf("%d",&w[i]);
	for(int i=1;i<=n;i++){
		change(1,pre[i]+1,i,w[f[i]]);	
		if(pre[i])	change(1,pre[pre[i]]+1,pre[i],-w[f[i]]);
		res=max(res,t[1].mx);
	}
	cout<<res<<endl;
	return 0;
}