891. 子序列宽度之和

891.子序列宽度之和

题目描述：

一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

数据范围：

$1\le nums.len \le 10^5, 1\le nums[i] \le 10^5$

题解：

排序，排序之后枚举起点 $a_i$ ，可以得到对答案的贡献为

$a_i - a_i + a_{i + 1} - a_i + 2^1\times (a_{i + 1} - a_i) + 2^2 \times (a_{i + 2} - a_i) + \cdots$

第一项为 $0$ 。可以发现后面可以拆分成一个可以递推的，一个等比数列和。

等比数列为 $a_i,a_{i + 1},a_{i +2},\cdots,a_{n - 1}$ 。故前 $n$ 项和为 $a_i \times \frac{1-2^{n - 1 - (i + 1) + 1}}{1-2} = a_i \times (2^{n - i - 1} - 1)$ 。

递推的为 $sum \times 2 + nums [i + 1]$ 。

所以可以先预处理出 $2^i$ 次方，后面直接从后往前递推即可。

不能用子数组那种处理方法，子数组是使用dp或者也是考虑贡献。使用单调栈处理每个数贡献的长度，但是子序列的话，可能和当前长度之外的也会产生贡献，就会有问题。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const long long mod = 1e9 + 7;
    int sumSubseqWidths(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (nums.size() == 1)
            return 0;
        long long ans = 0;
        long long sum = 0;
        vector<long long> pow2i(n);
        pow2i[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            pow2i[i] = 2 * pow2i[i - 1] % mod;
        }
        for (int i = n - 1; i >= 0; --i)
        {
            if (i + 1 == n)
                sum = 0;
            else
                sum = (sum * 2 + nums[i + 1]) % mod;
            ans = (ans + sum - (pow2i[n - i - 1] - 1) * nums[i] % mod + mod) % mod;
        }
        return ans;
    }
};