u群看见的题

· · 个人记录

orz myh jly

题意:给 n 个数，每次选出一个大小在 [L,R] 之间的子集，求前 k 大的子集和的和. n,k\leq 2\times 10^5.

从小到大排序，那么对于长度为 len 的子集，最小的显然是 [1,len] 构成的，然后应该是选出一段后缀向右平移一格，得到不超过两段数，再然后依然是选出靠后的一段后缀向右平移一格.那么我们发现这个转移构成了一棵树，可以使用堆维护，每次删掉最小的加入其最小的儿子和比它大的最小的兄弟. 于是只需要维护每一个状态的父亲的最后一段长度、该状态的最后一段长度以及该状态最右边的位置即可.复杂度 O(k\log n)