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],…,f[n](1<=f[i]<=m)。
第三行包含m个整数w[1],w[2],…,w[m](1<=w[j]<=1000000)。
Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。
Sample Input
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
2 3 1 1 4 1 2 4 1
5 3 6 6
Sample Output
15
Hint
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
题解
这道题稀里糊涂的写了一个下午，思路什么的乱七八糟的...回家理清思路，半个小时就写完了。
我们枚举区间左端点，线段树维护每个位置作为右端点的答案，
$nex[i]$记录第$i$天的电影下次播放时间
当我们往右移的时候，显然$i$这个点的颜色已经不会为之后的区间有加成，我们需要将$i$~$nex[i]-1$这一段区间减掉$w[f[i]]$。
同样，当我们左端点右移的时候，将迎接一个新的$f[i]$，那么我们就要将$nex[i]$~$nex[nex[i]]-1$这一段区间加上$w[f[i]]$。
线段树维护，支持区间修改以及查询最大值。
注意一开始的时候就把所有颜色的最左的一段加入线段树中。
//It is made by Awson on 2017.10.16
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define sqr(x) ((x)*(x))
#define Lr(o) (o<<1)
#define Rr(o) (o<<1|1)
using namespace std;
const int N = ;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
} struct segment {
LL sgm[(N<<)+], lazy[(N<<)+];
void pushdown(int o) {
sgm[Lr(o)] += lazy[o], sgm[Rr(o)] += lazy[o];
lazy[Lr(o)] += lazy[o], lazy[Rr(o)] += lazy[o];
lazy[o] = ;
}
void update(int o, int l, int r, int a, int b, int key) {
if (a <= l && r <= b) {
sgm[o] += key, lazy[o] += key;
return;
}
pushdown(o);
int mid = (l+r)>>;
if (a <= mid) update(Lr(o), l, mid, a, b, key);
if (b > mid) update(Rr(o), mid+, r, a, b, key);
sgm[o] = Max(sgm[Lr(o)], sgm[Rr(o)]);
}
}T; int n, m, f[N+], w[N+];
int path[N+], nex[N+]; void work() {
read(n), read(m);
for (int i = ; i <= n; i++) read(f[i]);
for (int i = ; i <= m; i++) read(w[i]);
for (int i = n; i >= ; i--) {
nex[i] = path[f[i]], path[f[i]] = i;
}
for (int i = ; i <= m; i++) if (path[i]) {
if (nex[path[i]]) T.update(, , n, path[i], nex[path[i]]-, w[i]);
else T.update(, , n, path[i], n, w[i]);
}
LL ans = ;
for (int i = ; i <= n; i++) {
ans = Max(ans, T.sgm[]);
if (nex[i]) {
T.update(, , n, i, nex[i]-, -w[f[i]]);
if (nex[nex[i]]) T.update(, , n, nex[i], nex[nex[i]]-, w[f[i]]);
else T.update(, , n, nex[i], n, w[f[i]]);
}else T.update(, , n, i, n, -w[f[i]]);
}
printf("%lld\n", ans);
}
int main() {
work();
return ;
}