CF1621G Solution
考虑对每个位置 \(i\) 作为 \(i_j\) 时计算贡献。\(i\) 对一次答案有贡献当且仅当:
-
设其子序列内最右端的位置为 \(r\),则要满足 \(r\) 右侧存在一个数大于 \(a_{i}\)。
-
即,设 \(lst_i\) 表示整个序列最右侧的大于 \(a_i\) 的数,要满足 \(lst_i>r\)。
现在,对于每个 \(i\) 我们要求包含它且右端点小于 \(lst_i\) 的上升子序列个数。
\(i\) 左侧包含 \(i\) 的子序列个数容易计算,那么现在求右侧的子序列个数,乘起来就好了。
右侧要满足:以 \(i\) 开头,右端点小于 \(r=lst_i\)。这个可能有点麻烦,我们用总的减去不合法的,即先求出 \(i\) 右侧包含 \(i\) 的所有子序列个数,减去 \(i\) 开头 \(r\) 结尾的上升子序列个数。(右端点不可能大于 \(r\),因为 \(r\) 之后的都小于 \(a_i\))
对于所有的 \(i\) 我们可以得到若干个 \(r\),这些 \(r\) 恰好是序列的后缀最大值位置。设 \(suf_i\) 表示从后往前第 \(i\) 个后缀最大值位置。
那么对于一个后缀最大值位置 \(r=suf_i\),满足 \(lst_i=r\) 的所有 \(i\) 需要满足:\(a_i\in[a_{suf_{i-1}},a_{suf_i})\)。
这样把所有 \(a\) 划分为若干个互不相交的区间。由于以 \(i\) 开头以 \(r\) 结尾的上升子序列中间的数一定在 \([a_i,a_r]\) 中,我们枚举每个后缀最大值位置,把满足 \(a_i\in[a_{suf_{i-1}},a_{suf_i})\) 的所有 \(i\) 拉出来,求一遍上升子序列即可。
复杂度 \(\mathcal O(n\log n)\)。
标签:suf,cf1621g,后缀,个数,solution,lst,序列,右侧 From: https://www.cnblogs.com/iorit/p/18040129