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],…,fn。
第三行包含m个整数w[1],w[2],…,wm。
Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。
Sample Input
9 4
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。
题解
枚举每一天作为右端点
记第i天上一次和他放同样电影的一天是pre[i]
显然pre[i]+1~i这段区间里这天放的电影才会有贡献
把pre[pre[i]]+1~pre[i]的贡献去掉 pre[i]+1~i的贡献加上
线段树查找最大值即可
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #define LL long long #define mp(x,y) make_pair(x,y) #define lc now<<1 #define rc now<<1|1 using namespace std; inline int read() {
int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
write(x);printf(" ");} LL mx[4110000],lazy[4110000]; void upd(int now) {
if(!lazy[now])return ;mx[lc]+=lazy[now];lazy[lc]+=lazy[now];mx[rc]+=lazy[now];lazy[rc]+=lazy[now];lazy[now]=0; } void modify(int now,int l,int r,int ql,int qr,LL c) {
if(ql>qr)return ;if(l==ql&&r==qr){
mx[now]+=c;lazy[now]+=c;return ;}int mid=(l+r)/2;upd(now);if(qr<=mid)modify(lc,l,mid,ql,qr,c);else if(mid+1<=ql)modify(rc,mid+1,r,ql,qr,c);else modify(lc,l,mid,ql,mid,c),modify(rc,mid+1,r,mid+1,qr,c);mx[now]=max(mx[lc],mx[rc]); } LL findmax(int now,int l,int r,int ql,int qr) {
if(ql>qr)return 0;if(l==ql&&r==qr)return mx[now];int mid=(l+r)/2;upd(now);if(qr<=mid)return findmax(lc,l,mid,ql,qr);else if(mid+1<=ql)return findmax(rc,mid+1,r,ql,qr);else return max(findmax(lc,l,mid,ql,mid),findmax(rc,mid+1,r,mid+1,qr)); } int n,m; int hh[1110000],pre[1110000]; int a[1110000]; int w[1110000]; int main() {
n=read();m=read();memset(hh,-1,sizeof(hh));for(int i=1;i<=n;i++){
a[i]=read();pre[i]=hh[a[i]];hh[a[i]]=i;}LL s=0,ans=0;for(int i=1;i<=m;i++)w[i]=read();for(int i=1;i<=n;i++){
modify(1,0,n,pre[i]+1,i,w[a[i]]);if(pre[pre[i]])modify(1,0,n,pre[pre[i]]+1,pre[i],-w[a[i]]);ans=max(ans,findmax(1,0,n,0,i));}printf("%lld\n",ans);return 0; }