[POI]2015 Kinoman

好题!

讲真的这道题比较有代表性,比较套路?(bushi考试的时候没写出来(tcl )，菜是原罪

题意:

给你一个序列，序列上每一个元素都属于一种种类，并且每一种元素有其对应的价值，你可以任意取一段区间,计算这段区间中没有重复出现的元素种类的价值之和.你需要最大化这个价值之和.

思路:

这道题看上去就很让我懵逼，不知道该怎么维护"没有重复出现的元素种类"......

思路一: 直接枚举每一个区间+暴力计算，时间复杂度　O(n ^ 3),得分23分

思路二：枚举每一个左端点，不断将右端点往右边移动，记录一下移动过程中得到的价值之和的最大值,时间复杂度O(n ^ 2),得分40 分　

思路三:

考虑枚举每一个右端点，记录一下每个位置对应的种类上一次出现的位置.
对于右端点向右边移动的操作,假设当前种类是i,将区间[pre[i]+1,i]加上i的价值,
将区间[pre[pre[i]]+1,pre[i]]减去i的价值,同时求一下区间[1,i]最大值就行了,时间复杂度O(nlogn)
得分:100pts

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int mp[1000005];
int a[1000005],f[1000005];
int pre[1000005];
int n,m;
struct node{
	int l,r,Max,laz;
}T[4000005];
void build(int x,int l,int r)
{
	T[x].l = l , T[x].r = r;
	T[x].Max = 0;
	if(T[x].l == T[x].r)return ;
	int mid = (l + r) >> 1;
	build(x << 1 , l , mid);
	build(x << 1 | 1 , mid + 1 , r );
	return ;
}
void ad(int x,int k)
{
	T[x].Max += k;
	T[x].laz += k;	
}
void pushdown(int x)
{
	if(T[x].laz == 0)return ;
	ad(x << 1 , T[x].laz);
	ad(x << 1 | 1 , T[x].laz);
	T[x].laz = 0;
	return ;
}
void change(int x,int l,int r,int k)
{
	if(T[x].l >= l && T[x].r <= r){ad(x,k);return ;}
	pushdown(x);
	int mid = (T[x].l + T[x].r) >> 1;
	if(l <= mid)change(x << 1 , l , r , k);
	if(r  > mid)change(x << 1 | 1 , l , r , k);
	T[x].Max = max(T[x << 1].Max , T[x << 1 | 1].Max);
}
int getMax(int x,int l,int r)
{
	int Max = 0;
	if(T[x].l >= l && T[x].r <= r)return T[x].Max;
	pushdown(x);
	int mid = (T[x].l + T[x].r) >> 1;
	if( l <= mid )Max = max(Max,getMax(x << 1 , l , r ));
	if( r  > mid )Max = max(Max,getMax(x << 1 | 1 , l , r ));
	return Max;
}
inline int read(){
	int x = 0 ,flag = 1;
	char ch = getchar();
	for( ; ch > '9' || ch < '0' ; ch = getchar())if(ch == '-')flag = -1;
	for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
	return x * flag;
}
signed main()
{
	n = read(),m = read();
	int M = 0;
	for(int i = 1 ; i <= n ; i ++)
		a[i] = read();
	for(int j = 1 ; j <= m ; j ++)
		f[j] = read();
	for(int i = 1 ; i <= n ; i ++)
	{
		if(mp[a[i]] != 0)pre[i] = mp[a[i]];
		mp[a[i]] = i;
	}
	build(1 , 1 , n);
	for(int i = 1 ; i <= n ; i ++)
	{
		if(pre[i]){
			change(1 , pre[i] + 1 , i , f[a[i]]);
			change(1 , pre[pre[i]] + 1 , pre[i] , -f[a[i]]);
		}
		else change(1, 1 , i , f[a[i]]);
		M = max(getMax(1,1,i),M);
	}
	cout << M;
	return 0;
}