[洛谷P3582] POI2015 KIN

问题描述

共有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

说明

共有m部电影，编号为1~m，第i部电影的好看值为w[i]。

在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。

你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

解析

如果不计重复的话，这道题就是求最大子段和的问题。但是，现在牵涉到重复的不能计入贡献的问题。我们可以选择在每次遇到一个前面出现过的元素，就把前面那个相同的贡献改为-1。不妨记前面与i种类相同的元素位置为\(pre[i]\)，如果\(pre[i]\)之前还有与它相同的，就把\(pre[i]\)前面的贡献改为0。所以，我们需要用线段树维护最大子段和，支持动态修改贡献。

这样做的问题在于修改后前面统计的答案是错误的。因此，我们可以在每次修改贡献之前都更新一次答案，这样就避免了这种问题。

代码

#include <iostream>
#include <cstdio>
#define int long long
#define N 1000002
using namespace std;
struct SegmentTree{
    int dat,sum,l,r;
}t[N*4];
int n,m,i,a[N],w[N],pre[N],last[N];
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;
}
void update(int p)
{
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].l=max(t[p*2].l,t[p*2].sum+t[p*2+1].l);
    t[p].r=max(t[p*2+1].r,t[p*2+1].sum+t[p*2].r);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].r+t[p*2+1].l);
}
void change(int p,int l,int r,int x,int val)
{
    if(l==r){
        t[p].dat=t[p].sum=t[p].l=t[p].r=val;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid) change(p*2,l,mid,x,val);
    else change(p*2+1,mid+1,r,x,val);
    update(p);
}
signed main()
{
    n=read();m=read();
    for(i=1;i<=n;i++) a[i]=read();
    for(i=1;i<=m;i++) w[i]=read();
    int ans=0;
    for(i=1;i<=n;i++){
        pre[i]=last[a[i]];
        last[a[i]]=i;
        if(pre[i]) change(1,1,n,pre[i],-w[a[i]]);
        if(pre[pre[i]]) change(1,1,n,pre[pre[i]],0);
        change(1,1,n,i,w[a[i]]);
        ans=max(ans,t[1].dat);
    }
    printf("%lld\n",ans);
    return 0;
}

[洛谷P3582] POI2015 KIN

原文：https://www.cnblogs.com/LSlzf/p/11746961.html