「BZOJ-3747」POI-2015Kinoman-ZKW 线段树

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

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

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

链接

BZOJ-3747

题解

$next[i]$ 记录第 $i$ 天的电影下次播放时间，枚举区间左端点，线段树维护每个位置作为右端点的答案，考虑 $l - r$ 的左端点变为 $l + 1$，发现 $l$ 到 $next[l] - 1$ 的答案减少 $w[f[l]]$，而 $next[l]$ 到 $next[next[l]] - 1$ 增加 $w[f[l]]$，用线段树维护就好了，支持区间修改以及查询最大值，果断写了发 ZKW。

/*
 * created by xehoth on 17-04-2017
 */
#include <bits/stdc++.h>

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    if (s == t) {
        t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
        if (s == t) return -1;
    }
    return *s++;
}

template<class T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        if (c == '-') iosig = true;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    if (iosig) x = -x;
}

namespace SegmentTree {

const int MAXN = 1000005;

#define long long long

struct Node {
    long max, add;
} d[1048576 * 2 + 1];

int M;

inline void maintain(int k) {
    d[k].max = std::max(d[k << 1].max, d[k << 1 | 1].max);
}

inline void build(const int n) {
    for (M = 1; M < n + 2; M <<= 1);
}

inline void cover(int k, long v) {
    d[k].max += v, d[k].add += v;
}

inline void pushDown(int k) {
    if (d[k].add && k <= M) {
        (k << 1) ? (cover(k << 1, d[k].add), 0) : 0;
        (k << 1 | 1) ? (cover(k << 1 | 1, d[k].add), 0) : 0;
        d[k].add = 0;
    }
}

inline void update(int k) {
    static int st[25], top;
    for (top = 0; k; k >>= 1) st[++top] = k;
    while (top--) pushDown(st[top]);
}

inline void modify(int s, int t, int v) {
    register int l = 0, r = 0;
    for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
        (~s & 1) ? (l ? 0 : (update(l = s ^ 1), 0), cover(s ^ 1, v), 0) : 0;
        (t & 1) ? (r ? 0 : (update(r = t ^ 1), 0), cover(t ^ 1, v), 0) : 0;
    }
    for (l >>= 1; l; l >>= 1) maintain(l);
    for (r >>= 1; r; r >>= 1) maintain(r);
}

inline void solve() {
    register int n, m;
    static int f[MAXN], w[MAXN], next[MAXN], last[MAXN];
    read(n), read(m);
    for (register int i = 1; i <= n; i++) read(f[i]);
    for (register int i = 1; i <= m; i++) read(w[i]);
    for (register int i = n; i; i--) next[i] = last[f[i]], last[f[i]] = i;
    build(n);
    for (register int i = 1; i <= m; i++) {
        if (last[i]) {
            if (!next[last[i]]) modify(last[i], n, w[i]);
            else modify(last[i], next[last[i]] - 1, w[i]);
        }
    }
    register long ans = 0;
    for (register int i = 1; i <= n; i++) {
        ans = std::max(ans, d[1].max);
        register int t = next[i];
        if (t) {
            modify(i, t - 1, -w[f[i]]);
            if (next[t]) modify(t, next[t] - 1, w[f[i]]);
            else modify(t, n, w[f[i]]);
        } else {
            modify(i, n, -w[f[i]]);
        }
    }
    printf("%lld\n", ans);
}
}

int main() {
    SegmentTree::solve();
    return 0;
}