第k小（大）子序列和

非负数序列的第 k 小子序列和

先把所有数从小到大排序。设一个二元组 (sum, i) 表示以第 i 位为结尾，和为 sum 的子序列，用一个小根堆来维护这些二元组，以(arr[0], 0)为初始二元组，每次取出堆顶，然后把 (sum+arr[i+1], i+1) 和 (sum+arr[i+1]−arr[i], i+1) 加入堆中，以此来生成所有的子序列和，而且生成步骤每次都是取出当前最小的。

所以第 k 个被取出的堆顶就是答案。

PS: 虽然上述步骤可以逐个生成所有的第k小子序列和，但若len(arr) = n，因为arr中每个数都可以出现在序列或不出现在序列，因为共有2^{n种组合，因为k的范围是很大的，而算法的复杂度是O(nlogn)+O(klogk)，所以k的实际上是受限的，一般不能超过10}5

第 k 小子序列和（允许有负数）

当序列中有负数时，我们还是用前面的思路从最小和序列逐个生成，而这时最小和序列是包含所有负数的子序列，生成的过程是不断去掉一个负数或者加上一个正数情况会变得复杂，我们可以先算出所有负数的和作为最小和min_sum，其他的和都是在这个基础上减去一些正数或加上一些负数生成的，当arr[i]是负数时因为已经在最小基础和min_sum里了，在生成新和时总是减掉这个负数相当于加上负数的绝对值，而当arr[i]是正数时因为不在min_sum里，在生成新和时总是加上正数，因此我们可以把正负数统一按绝对值处理，用min_sum加上序列abs(arr)的某个子序列和，就是原序列的相应的子序列和，序列abs(arr)是arr的绝对值形成的序列，它的子序列和则可以规约到前面已经讨论过的非负数序列的第 k 小子序列和问题了。

第 k 大子序列和（允许有负数）

因为第k小子序列和的k受限，本问题不能简单规约到第2^n-1-k小子序列和解决，

我们可以先算出所有正数的和作为最大和max_sum，其他的和都是在这个基础上减去一些正数或加上一些负数生成的。

我们还是可以把正负数统一处理，我们可以把问题规约为 max_sum - kMinSum(abs(arr), k)，其中abs(arr)表示对arr中每个元素取绝对值形成的数组。

typedef long long ll;

struct Node {
    ll sum;
    int i;
};

// 求非负整数数组nums的第k小子序列和，k=0,1,2,...,2^n-1
// 算法复杂度是O(nlogn)+O(klogk), n=nums.size()
// 所以n和k的规模都是受限的，一般不能超过10^5
ll kMinSumBase(const vector<int>& nums, int k) {
    vector<int> arr = nums;
    sort(arr.begin(), arr.end());
    auto cmp = [&](const Node& a, const Node& b) {
        return a.sum > b.sum;
    };
    priority_queue<Node, vector<Node>, decltype(cmp)> PQ(cmp);
    PQ.push(Node{arr[0], 0});
    PQ.push(Node{0, -1}); // 特殊处理空子段
    ll result = 0;
    for(int i=0;i<k && !PQ.empty();i++) {
        auto node = PQ.top(); PQ.pop();
        if(node.i != -1 && node.i+1 < arr.size()) {
            PQ.push(Node{node.sum+arr[node.i+1], node.i+1});
            PQ.push(Node{node.sum+arr[node.i+1]-arr[node.i], node.i+1});
        }
    }
    assert(!PQ.empty());
    auto node = PQ.top(); PQ.pop();
    return node.sum;
}

// 求数组nums（允许有负数）的第k小子序列和，k=0,1,2,...,2^n-1
// n和k的规模都是受限的，一般不能超过10^5
ll kMinSum(const vector<int>& nums, int k) {
    ll min_sum = 0;
    vector<int> arr(nums.size());
    for(int i=0;i<nums.size();i++) {
        if(nums[i] < 0) {
            min_sum += nums[i];
        }
        arr[i] = abs(nums[i]);
    }
    return min_sum + kMinSumBase(arr, k);
}

// 求数组nums（允许有负数）的第k大子序列和，k=0,1,2,...,2^n-1
// n和k的规模都是受限的，一般不能超过10^5
ll kMaxSum(const vector<int>& nums, int k) {
    ll max_sum = 0;
    vector<int> arr(nums.size());
    for(int i=0;i<nums.size();i++) {
        if(nums[i] > 0) {
            max_sum += nums[i];
        }
        arr[i] = abs(nums[i]);
    }
    return max_sum - kMinSumBase(arr, k);
}