加权上升子序列 (Weighted Increasing Subsequences, CF1621G)

你有一个长度为\(n(1\leq n\leq 2\times 10^5)\)的整数列\(a(1\leq a_i\leq 10^9)\). \(a_{i_1},...,a_{i_k}\)是\(a\)的一个严格上升子序列, 它的权定义为满足以下条件的下标\(j\)的个数:

\((1)\) \(1\leq j\leq k\).

\((2)\) 存在下标\(x\), 满足\(i_k<x\leq n\), 且\(a_x>a_{i_j}\).

求\(a\)的所有严格上升子序列的权值之和. 答案对\(10^9+7\)取模.

[分析]

我们考虑下标\(i\)对答案的贡献. 记\(j\)为最大的满足\(a_j>a_i(j>i)\)的下标. 如果这样的\(j\)不存在, 那么\(i\)对答案的贡献为\(0\). 考虑所有对答案贡献不为\(0\)的下标\(i\). 根据\(j\)的定义, 我们知道\(a_j\)后面的元素都不大于\(a_i\), 因此它们不可能包含在下标集合包含\(i\)的严格上升子序列内. 于是在所有下标集合包含\(i\)的严格上升子序列中, \(i\)对答案有贡献当且仅当下标集合不包含\(j\). 因此我们得到如下结论:

下标\(i\)对答案的贡献 \(=\) 下标集合包含\(i\)的严格上升子序列数 \(-\) 下标集合包含\(i\)和\(j\)的严格上升子序列数(下标\(i\)对应的下标\(j\)不存在则下标\(i\)对答案的贡献直接为\(0\)).

记\(lef_i\)表示最后一个下标为\(i\)的严格上升子序列数, \(rig_i\)表示第一个下标为\(i\)的严格上升子序列数. 对\(a_i\)进行离散化处理以后, 用树状数组\(C_u\)表示最后一个元素为\(u\)的严格上升子序列个数, 顺序枚举\(i\)并维护\(C_u\)即可求出所有\(lef_i\); 用树状数组\(D_u\)表示第一个元素为\(u\)的严格上升子序列个数, 逆序枚举\(i\)并维护\(D_u\)即可求出所有\(rig_i\). 于是下标集合包含\(i\)的严格上升子序列数 \(=\) \(lef_i\times rig_i\). 下标集合包含\(i\)和\(j\)的严格上升子序列数 \(=\) \(lef_i\times\)以\(i\)为第一个下标, \(j\)为最后一个下标的严格上升序列数.

现在问题只剩下求起始于下标\(i\), 终止于下标\(j\)的严格上升子序列数. 我们现在考虑每个\(j\)能够被哪些\(i\)所对应. 设\(mx_j=\max\limits_{j<k\leq n}(a_k)\). 如果\(mx_j\geq a_j\), 则\(j\)不能够被任何\(i\)所对应(因为后面有一个下标大于\(j\)且值不小于\(a_j\)的数). 如果\(mx_j<a_j\), 则所有满足\(i<j,mx_j\leq a_i<a_j\)的下标\(i\)都对应于\(j\). 将所有这样的\(a_i\)组成一个子数组\(a'\). 在这个子数组中, 用\(rig'_i\)表示第一个下标为\(i\)的严格上升子序列数(可以类似于求\(rig_i\)的方法得到), 则在\(a'\)中, 以下标\(i\)开头的严格上升子序列后面加上\(a_j\)就是在原数组中下标以\(i\)开头, 以\(j\)结尾的严格上升子序列. 因此原数组中下标以\(i\)开头, 以\(j\)结尾的严格上升子序列个数就是\(rig'_i\). 由于每个\(i\)对应的\(j\)是唯一的, 因此每个\(i\)至多会在一个子数组\(a'\)中被计算. 所以总时间复杂度为\(O(nlogn)\).