洛谷P3582 [POI2015]KIN 题解

又是蒟蒻水题解的地方

$\texttt{Description}$

题面友好，不做解释

$\texttt{Solution}$

考试的时候没做出来。赛后才知道这是一个套路题。

对于这种“选出一段区间，要求总贡献最大”的题目，尝试沿用这样一种思路：从左往右枚举左端点，快速找到最优的右端点。本题我从右往左扫，因为比较方便。

$nxt_i$ 表示第 $i$ 部电影后面的第一部与它相同的电影在第几天放映。

然后从右往左枚举区间左端点，线段树维护对于当前的左端点，每个右端点能得到的贡献。当右端点由 $r+1$ 变为 $r$ 时，将 $[r,nxt_r)$ 区间加上 $w_{f_i}$，将 $nxt_{nxt_i}$ 区间减少 $w_{f_i}$。这个比较容易理解。

$\texttt{Code}$

#include <cstdio>
#define int long long

inline int max(const int x, const int y) {return x > y ? x : y;}
struct Node {
	int l, r, v, Lazy;
} c[4000005];
int wow[4000005];
void make_tree(const int O, const int L, const int R) {
	c[O].l = L, c[O].r = R;
	if (L != R) make_tree(O << 1, L, L + R >> 1), make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
}
void pushdown(const int O) {
	c[O << 1].v += c[O].Lazy, c[O << 1 | 1].v += c[O].Lazy;
	c[O << 1].Lazy += c[O].Lazy, c[O << 1 | 1].Lazy += c[O].Lazy;
	c[O].Lazy = 0;
}
void update(const int O, const int L, const int R, const int d) {
	if (L <= c[O].l && c[O].r <= R) {c[O].Lazy += d, c[O].v += d; return;}
	int mid(c[O].l + c[O].r >> 1);
	pushdown(O);
	if (L <= mid) update(O << 1, L, R, d);
	if (mid < R) update(O << 1 | 1, L, R, d);
	c[O].v = max(c[O << 1].v, c[O << 1 | 1].v);
}
int f[1000005], w[1000005], nxt[1000005], pre[1000005];

signed main() {
	int n, m, ans(0LL);
	scanf("%lld%lld", &n, &m);
	for (int i(1); i <= n; ++ i) scanf("%lld", f + i);
	for (int i(1); i <= m; ++ i) scanf("%lld", w + i);
	for (int i(1); i <= n; ++ i) nxt[pre[f[i]]] = i, pre[f[i]] = i;
	make_tree(1, 1, n);
	for (int i(n); i; -- i)  {//枚举右端点
		if (nxt[i]) update(1LL, i, nxt[i] - 1LL, w[f[i]]);
		else update(1LL, i, n, w[f[i]]);//特判边界
		if (nxt[i]) {
			if (nxt[nxt[i]]) update(1LL, nxt[i], nxt[nxt[i]] - 1LL, -w[f[i]]);
			else update(1LL, nxt[i], n, -w[f[i]]);//特判边界
		}
		ans = max(ans, c[1].v);//由于是整体取最大值，可以少写一个查询函数，直接取根节点的值即可
	}
	printf("%lld", ans);
	return 0;
}

$\texttt{Summary}$

这种经典的套路题还是有必要总结一下的。

首先，这种“选择一段区间，使其总贡献最大/总花费最小”的题目，应该立即反应到枚举左端点，快速找到最优右端点的方法。典型如UVA1471

其次，类似“重复的只算一次”（本题一次都不算），”求种类数”的题，一般是记录 $nxt_i$ 表示第 $i$ 个“数”后面与它种类相同的“数”，然后采用树状数组/线段树等支持区修区查或单修区查的数据结构来维护对应右端点的取值。典型如HH的项链

end.