简要题意

给出一个长度为 $n$ 个二元组 $(f_i,w_{f_i})$。求出其的最大子段 $w_{f_i}$ 和，$f_i$ 出现多次的 $w_{f_i}$ 不对答案产生贡献。

$1\leq n,f_i,w_i\leq 10^6$

思路

给一个貌似不一样的做法。我们换一个视角看最大子段和。

首先考虑最大子段和到底是什么。序列 $a$ 的最大子段和形式化定义为：

记 $b$ 为 $a$ 的 后缀和，则可以变形为：

交换 $\max$ 顺序得：

我们可以用线段树维护后面那个差分的形式，然后枚举 $R$ 扫一遍即可。

具体来说考虑每加入一个 $a_i$，记 $c_i$ 为当前 $L=i$ 的差分，则可以将区间 $[1,i]$ 内的所有 $j$，$c_j$ 加上 $a_i$。然后维护一个区间最大值即可。时间复杂度是 $O(n\log n)$。

回到这道题，关键在于如何剔除重复元素的贡献。

给一个图：

假设现在需要加入第 $A$ 个元素。考虑记录它前面第一个与它相同的元素是第 $B$ 个，第二个是第 $C$ 个。

则位于 $[B+1,A]$ 区间（粉色段）的后缀和无需剔除贡献（因为只有 $A$ 一个元素），而是需要加入 $A$ 的贡献。所以我们对区间 $[B+1,A]$ 的后缀和加上 $w_{f_{A}}$。

位于 $[1,B]$ 区间的后缀和需要剔除贡献，但是我们只需要剔除 $[C+1, B]$ 区间（蓝色段）的贡献就好了。也就是对区间 $[C+1, B]$ 的后缀和减去 $w_{f_A}$。

为什么呢？因为 $[1,C]$ 原本是没有贡献的，因为加入 $B$ 的时候（以及 $B$ 之前的元素）已经将这一段剔除了（因为包含了 $B,C$ 至少两个相同的元素）。而 $[C+1,B]$ 是我们在加入 $B$ 的时候特意保留增加了贡献的（具体参考我们第一个进行的操作），所以要剔除。

$C,B$ 用两个桶就可以维护。所以时间复杂度仍然是 $O(n\log n)$。去掉线段树部分，关键逻辑部分出乎意料的短。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
using namespace std;

const int N = 1e6 + 5;
int n,m,f[N],w[N], bkt[N], bkt2[N], ans = LLONG_MIN;
int t[N << 2], tag[N << 2];

void pushup(int i){t[i] = max(t[ls], t[rs]);}

void pushdown(int i){
    if(tag[i]){
        tag[ls] += tag[i];tag[rs] += tag[i];
        t[ls] += tag[i];t[rs] += tag[i];
        tag[i] = 0;
    }
}

void update(int ql, int qr, int v, int i, int l, int r){
    if(ql <= l && r <= qr){
        t[i] += v, tag[i] += v;
        return;
    }
    pushdown(i);
    if(ql <= mid) update(ql, qr, v, ls, l, mid);
    if(qr > mid) update(ql, qr, v, rs, mid + 1, r);
    pushup(i);
}

int query(int ql, int qr, int i, int l, int r){
    if(ql <= l && r <= qr) return t[i];
    pushdown(i);
    int ans = LLONG_MIN;
    if(ql <= mid) ans = max(ans, query(ql, qr, ls, l, mid));
    if(qr > mid) ans = max(ans, query(ql, qr, rs, mid + 1, r));
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1;i<=m;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        update(bkt[f[i]] + 1, i, w[f[i]], 1, 1, n);
        if(bkt[f[i]]) update(bkt2[bkt[f[i]]] + 1, bkt[f[i]], -w[f[i]], 1, 1, n);
        bkt2[i] = bkt[f[i]];bkt[f[i]] = i;
        ans = max(ans, query(1, i, 1, 1, n));
    }
    cout<<ans;
    return 0;
}