ZYCode R7 旅游 题解

ballpoint_pen · 2023-12-01 18:31:34 · 个人记录

• 一个点的旅游方案，一定是经过该点的推荐指数最大的 k_i 个景点按递增序排列。
• 考虑线段树合并，权值线段树记录指数为 x 的景点数量，查询答案可以线段树上二分。
• 对于每个线段树上的节点，维护区间中的数量，权值和，以及全选时的答案。（分别为 len,sm,ret）
• 树上差分，将每条路径挂到 4 个单点的修改上。

那么剩下的问题就只有：如何合并两个线段树节点。

设有这样两个线段树节点 p_1,p_2。令 p_1 在 p_2 左，即 p_2 中的点权值更大。

那么计算答案时只需将 p_2 整段拼到 p_1 右边，并重新计算贡献。不难得出合并后的节点 p 为：\{len_{p_1}+len_{p_2},sm_{p_1}+sm_{p_2},ret_{p_1}+ret_{p_2}+sm_{p_2}\times len_{p_1}\}。

于是做完了。