问题描述
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
输入格式
第一行两个整数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)。
输出格式
输出观看且仅观看过一次的电影的好看值的总和的最大值。
样例输入
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
样例输出
15
样例解释
15
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
链接
解析
考虑如何解决重复电影没有贡献的问题。记第(i)的电影前面一次出现的时候为(L[i])，后面一次出现的时候为(R[i])，那么这个电影能够计贡献的区间为([i,R[i]-1])。所以，我们把所有电影按照(L[i])排序，然后枚举选择区间的左端点，用线段树维护答案。每次将左端点以前的贡献在线段树中减掉，同时在满足条件的区间中加入(L[i])小于当前左端点的天的贡献。维护最大值即可。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1000002
using namespace std;
struct SegmentTree{
long long dat,add;
}t[N*4];
struct day{
int l,r,w,p;
}a[N],b[N];
int n,m,i,j,k,pos[N],f[N],w[N];
long long ans;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
int my_comp(const day &x,const day &y)
{
if(x.l==y.l) return x.p<y.p;
return x.l<y.l;
}
void spread(int p)
{
if(t[p].add){
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p*2].dat+=t[p].add;
t[p*2+1].dat+=t[p].add;
t[p].add=0;
}
}
void change(int p,int l,int r,int ql,int qr,int x)
{
if(ql<=l&&r<=qr){
t[p].dat+=x;
t[p].add+=x;
return;
}
int mid=(l+r)/2;
spread(p);
if(ql<=mid) change(p*2,l,mid,ql,qr,x);
if(qr>mid) change(p*2+1,mid+1,r,ql,qr,x);
t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}
signed main()
{
n=read();m=read();
for(i=1;i<=n;i++) f[i]=read();
for(i=1;i<=m;i++) w[i]=read();
for(i=1;i<=n;i++) a[i].w=w[f[i]],a[i].p=i;
for(i=1;i<=n;i++){
a[i].l=pos[f[i]];
pos[f[i]]=i;
}
memset(pos,0,sizeof(pos));
for(i=n;i>=1;i--){
a[i].r=pos[f[i]]==0?n+1:pos[f[i]];
pos[f[i]]=i;
}
for(i=1;i<=n;i++) b[i]=a[i];
sort(a+1,a+n+1,my_comp);
j=k=1;
for(i=1;i<=n;i++){
if(i>1) change(1,1,n,b[i-1].p,b[i-1].r-1,-b[i-1].w);
while(a[j].l<i&&j<=n) change(1,1,n,a[j].p,a[j].r-1,a[j].w),j++;
ans=max(ans,t[1].dat);
}
printf("%lld
",ans);
return 0;
}