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
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
题解
线段树经典题
nxt[i]记录第i天的电影下次播放时间
枚举区间左端点，线段树维护每个位置作为右端点的答案
考虑l-r的左端点变为l+1
发现l到nxt[l]-1的答案减少w[f[l]]
而nxt[l]到nxt[nxt[l]]-1增加w[f[l]]
线段树维护，支持区间修改以及查询最大值
其实记录一段区间直接去修改边，每个数值都加，每个数值都减去。
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std; int n,m;
int f[],w[],last[],next[];
struct Node
{
ll mx,flag;
}tr[]; inline void pushdown(int p,int l,int r)
{
if (l==r) return;
ll flag=tr[p].flag;tr[p].flag=;
tr[p<<].flag+=flag;tr[p<<|].flag+=flag;
tr[p<<].mx+=flag;tr[p<<|].mx+=flag;
// cout<<flag<<endl;
}
void add(int p,int l,int r,int x,int y,int z)
{
if (tr[p].flag) pushdown(p,l,r);
if (l==x&&r==y)
{
tr[p].flag=z,tr[p].mx+=z;
return;
}
int mid=(l+r)>>;
if (y<=mid) add(p<<,l,mid,x,y,z);
else if (x>mid) add(p<<|,mid+,r,x,y,z);
else add(p<<,l,mid,x,mid,z),add(p<<|,mid+,r,mid+,y,z);
tr[p].mx=max(tr[p<<].mx,tr[p<<|].mx);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",&f[i]);
for (int i=;i<=m;i++)
scanf("%d",&w[i]);
for (int i=n;i>=;i--)
{
next[i]=last[f[i]];
last[f[i]]=i;
}
for (int i=;i<=m;i++)
{
if (last[i])
if (!next[last[i]]) add(,,n,last[i],n,w[i]);
else add(,,n,last[i],next[last[i]]-,w[i]);
// for (int j=1;j<=n;j++)
// cout<<tr[j].mx<<" ";
// cout<<endl;
}
ll ans=;
for (int i=;i<=n;i++)
{
ans=max(ans,tr[].mx);
int num=next[i];
if (num)
{
add(,,n,i,num-,-w[f[i]]);
if (next[num]) add(,,n,num,next[num]-,w[f[i]]);
else add(,,n,num,n,w[f[i]]);
}
else add(,,n,i,n,-w[f[i]]);
}
printf("%lld",ans);
}