P3582 [POI2015] KIN & ZLOJ 练习58 B()

written on 2022-08-03

套路题,是找最优区间的问题

对于这类问题,一般的方法是使用数据结构维护相关信息,然后枚举左/右端点,找到最优的另一端点。

难道不是极其套路的吗。。为什么连这都没做上来。。

那么具体到此题,由于同一种电影如果观看多于一次,其贡献就会为 \(0\),所以在枚举端点时是需要更新操作的。这里为了方便不妨使用强大的线段树。枚举左右端点均可,因此实际操作时我们不妨直接顺序枚举右端点,然后线段树中存的是以 \(x\) 为左端点的好看值,所以对于每一个右端点 \(i\),直接在线段树中查询 \(1\) ~ \(i\) 的最大值更新答案即可。

另外就是更新左端点答案的问题了。考虑区间向右扩展一格的影响,容易发现,此时:

  • \(1\) ~ \(i\) 的所有左端点加上 \(val_{a_i}\)。
  • \(1\) ~ \(lst_i\) 的所有左端点减去 \(val_{a_i}\)。

当然这是有问题的,因为重复更新(减去)了某一个值,事实上,可以手动模拟一下某个数据,可以总结发现,上述转移实际上应为:

  • \(lst_i+1\) ~ \(i\) 的所有左端点加上 \(val_{a_i}\)。
  • \(lst_{lst_i}+1\) ~ \(lst_i\) 的所有左端点减去 \(val_{a_i}\)。

当然正式比赛的时候还是应当自己手动调试分析来找结论的。这类题目十分套路,还是应当熟练掌握的。

————————

written on 2022-08-03

套路题,是找最优区间的问题

对于这类问题,一般的方法是使用数据结构维护相关信息,然后枚举左/右端点,找到最优的另一端点。

难道不是极其套路的吗。。为什么连这都没做上来。。

那么具体到此题,由于同一种电影如果观看多于一次,其贡献就会为 \(0\),所以在枚举端点时是需要更新操作的。这里为了方便不妨使用强大的线段树。枚举左右端点均可,因此实际操作时我们不妨直接顺序枚举右端点,然后线段树中存的是以 \(x\) 为左端点的好看值,所以对于每一个右端点 \(i\),直接在线段树中查询 \(1\) ~ \(i\) 的最大值更新答案即可。

另外就是更新左端点答案的问题了。考虑区间向右扩展一格的影响,容易发现,此时:

  • \(1\) ~ \(i\) 的所有左端点加上 \(val_{a_i}\)。
  • \(1\) ~ \(lst_i\) 的所有左端点减去 \(val_{a_i}\)。

当然这是有问题的,因为重复更新(减去)了某一个值,事实上,可以手动模拟一下某个数据,可以总结发现,上述转移实际上应为:

  • \(lst_i+1\) ~ \(i\) 的所有左端点加上 \(val_{a_i}\)。
  • \(lst_{lst_i}+1\) ~ \(lst_i\) 的所有左端点减去 \(val_{a_i}\)。

当然正式比赛的时候还是应当自己手动调试分析来找结论的。这类题目十分套路,还是应当熟练掌握的。