[POI 2015 R1] 影迷 Movie-goer 题解

思路

固定区间右端点 $r$，考虑每一个可能的左端点 $l$。我们希望维护区间 $[l,r]$ 中所有恰好出现一次的电影的好看值之和，并在所有 $l\le r$ 中取最大值。

设当天电影在此前最近两次出现的位置依次为 $p$ 和 $q$，不存在时记为零。加入新的右端点后：当 $p<l\le r$ 时，这部电影从没有出现变为出现一次，应增加其好看值；当 $q<l\le p$ 时，它从出现一次变为出现两次，应减去其好看值；更早的左端点对应的出现次数仍然至少为两次，贡献不变。

因此每加入一天，只需对两段连续的左端点区间做区间加法，再查询所有合法左端点的最大值。

做法

用线段树维护每个左端点当前对应的好看值总和，并支持区间加与区间最大值。按右端点从左到右扫描，利用每类电影最近两次的出现位置确定上述两个修改区间。完成修改后，查询左端点范围 $[1,r]$ 的最大值并更新答案。

对于 $n\le 2000$ 的子任务，可以枚举左端点，并向右扩展区间，利用出现次数在零、一次和两次之间的变化增减当前总和。若所有电影编号两两不同，观看完整的 $n$ 天即可获得所有出现电影的好看值之和。对于 $n\le 10^5$ 的子任务，可以按左端点分块，在整块上维护懒加标记和块内最大值，从而以平方根复杂度完成相同的两段区间修改。

复杂度

每个右端点只触发常数次线段树区间修改和最大值查询，时间复杂度为 $O(n\log n)$。线段树、电影序列和出现位置数组占用 $O(n+m)$ 空间。