Description：

有一排 $n$ 个数字，每个数字有价值，选一个区间 $[l,r]$ 最大化只出现过一次的数字的价值和。

$1\le n \le 10^6$

Solution：

像 $mex$ 那道题一样，用一个区间左指针从左往右扫，用线段树维护每个位置作为右端点的值。

刚开始的时候暴力建树，即如果有一个数字出现了第二次就把他减掉，之后就不管了。

然后区间左端点往右扫，记 $nxt[i]$ 表示位置 $i$ 上的数字下一次出现的位置，那么 $l$ 右移一位 $[l,nxt[l]-1]$ 的价值少了 $val[a[l]]$ ， $[nxt[l],nxt[nxt[l]]-1]$ 的价值增加了 $val[a[l]]$ ，这可以用线段树维护。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1000010

int a[MAXN],val[MAXN];

int nxt[MAXN],last[MAXN];

int cnt[MAXN];

typedef long long ll;

struct node

{

	int lc,rc;

	ll maxv,tag;

	node(){tag = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	t[t[rt].lc].maxv += t[rt].tag;t[t[rt].rc].maxv += t[rt].tag;

	t[t[rt].lc].tag += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,ll k,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].maxv += k;t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

ll query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].maxv;

	ll res = 0;

	if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= m;++i)scanf("%d",&val[i]);

	for(int i = 1;i <= n + 1;++i)last[i] = n + 1;

	for(int i = n;i >= 1;--i)

	{

		nxt[i] = last[a[i]];

		last[a[i]] = i;

	}

	build(root,1,n);

	for(ll i = 1,sum = 0;i <= n;++i)

	{

		if(cnt[a[i]] == 0)sum += val[a[i]];

		if(cnt[a[i]] == 1)sum -= val[a[i]];

		add(root,i,i,sum,1,n);

		++cnt[a[i]];

	}

	ll ans = 0;

	for(int l = 1;l <= n;)

	{

		ans = max(ans,query(root,l,n,1,n));

		add(root,l,nxt[l] - 1,-val[a[l]],1,n);

		add(root,nxt[l],nxt[nxt[l]] - 1,val[a[l]],1,n);

		++l;

	}

	cout << ans << endl;

	return 0;

}