BZOJ3747【POI2015】Kinoman <线段树>

Problem

【POI2015】Kinoman

$\mathrm{Time\;Limit:\;60\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

共有$m$部电影，编号为$1\sim m$，第$i$部电影的好看值为$w[i]$。
在$n$天之中（从$1\sim n$编号）每天会放映一部电影，第$i$天放映的是第$f[i]$部。
你可以选择$l,r\;(1\le l\le r\le n)$，并观看第$[l,r]$天内所有的电影。
如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。
你希望最大化观看且仅观看过一次的电影的好看值的总和。

Input

第一行两个整数$n,m\;(1\le m\le n\le 10^6)$。
第二行包含$n$个整数$f[1],f[2],…,f[n]\;(1\le f[i]\le m)$。
第三行包含$m$个整数$w[1],w[2],\cdots,w[m]\;(1\le w[j]\le10^6)$。

Output

输出观看且仅观看过一次的电影的好看值的总和的最大值。

Sample Input

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

Sample Output

15

Explanation

观看第$2,3,4,5,6,7$天内放映的电影，其中看且仅看过一次的电影的编号为$2,3,4$。

Source

鸣谢Jcvb

标签：线段树

Solution

暴力枚举左端点，考虑用线段树动态维护此时每个点作为右端点的答案的最大值。
先对每天预处理后面最早哪一天会放同样的电影，若后面不会再放，则令其为$n+1$。这个数组称为$nxt$。每种电影最先放映的时间称为$lst$（这是由于从后往前预处理，最先放映的在最后扫到）。
开始时，以$1$作为左端点，对于电影$i$，右端点在$[lst_i,nxt_{lst_i})$时$i$对答案有贡献，于是区间$[lst_i,nxt_{lst_i})$整体加$w_i$。此后每次将左端点向后移一天。设当前为第$i$天，则移到$i+1$后，区间$[i,nxt_i)$不会再有电影$f_i$的贡献，于是区间$[i,nxt_i)$整体减$w_{f_i}$。而区间$[nxt_i,nxt_{nxt_i})$则会有电影$f_i$的贡献，于是区间$[nxt_i,nxt_{nxt_i}]$区间加$w_{f_i}$。
每次移动左端点，并在线段树上修改，到下一个左端点后得到一个答案并和最大值打擂即可。时间复杂度$O(n\log{n})$。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, f[MAX_N+5], w[MAX_N+5];
int pos[MAX_N+5], nxt[MAX_N+5], cnt[MAX_N+5];
lnt tr[MAX_N<<2], tag[MAX_N<<2], ans;
void update(int v) {tr[v] = max(tr[v<<1], tr[v<<1|1]);}
void downtag(int v) {
    if (!tag[v]) return;
    tr[v<<1] += tag[v], tr[v<<1|1] += tag[v];
    tag[v<<1] += tag[v], tag[v<<1|1] += tag[v];
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, lnt x) {
    if (s >= l && t <= r) {tr[v] += x, tag[v] += x; return;}
    downtag(v);
    if (l <= mid) modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
    update(v);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(f[i]);
    for (int i = 1; i <= m; i++) read(w[i]);
    for (int i = n; i; i--) nxt[i] = pos[f[i]], pos[f[i]] = i;
    for (int i = 1; i <= m; i++) if (pos[i]) {
        if (!nxt[pos[i]]) modify(1, 1, n, pos[i], n, w[i]);
        else modify(1, 1, n, pos[i], nxt[pos[i]]-1, w[i]);
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, tr[1]);
        if (nxt[i]) {
            modify(1, 1, n, i, nxt[i]-1, -w[f[i]]);
            if (!nxt[nxt[i]]) modify(1, 1, n, nxt[i], n, w[f[i]]);
            else modify(1, 1, n, nxt[i], nxt[nxt[i]]-1, w[f[i]]);
        } else modify(1, 1, n, i, n, -w[f[i]]);
    }
    return printf("%lld\n", ans), 0;
}