本文共 2420 字，大约阅读时间需要 8 分钟。

题目大意：给定一个序列，求出k个这个序列的位置不完全相同的子序列，使得每一个子序列的长度均在[l,r]内，并且使得这些子序列的权值和最大。

思路：每一个子序列的权值和可以转化为两个前缀和之差。我们考虑以每一个位置为结尾的子序列，它的权值和可以看作是以该位置为结尾的前缀和减去它前面的某个前缀和。

那么想要这个子序列的权值和尽量大，那么就要前面的那个前缀和尽可能小。如果数目不够，就第2小。再不够，就第3小。

于是我们维护一个全局堆，分别表示以每个位置为结尾的最大子序列权值和，每次取出堆顶时再放进堆中一个结尾位置相同的第k+1大的权值和。

这样k次就能出解。

这要求我们能够快速求出区间第k小，利用可持久化线段树即可。

时间复杂度O(klogn).

Code:

#include 

转载地址：https://blog.csdn.net/wyfcyx_forever/article/details/40400327 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！