ZYCode R7 旅游 题解 最后更新于 2025-05-01 23:56:55

- 一个点的旅游方案，一定是经过该点的推荐指数最大的 $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}\}$。 于是做完了。