CF1621G Solution

iorit · 2023-05-04 11:56:20 · 个人记录

link

考虑对每个位置 i 作为 i_j 时计算贡献。i 对一次答案有贡献当且仅当：

设其子序列内最右端的位置为 r，则要满足 r 右侧存在一个数大于 a_{i}。
即，设 lst_i 表示整个序列最右侧的大于 a_i 的数，要满足 lst_i>r。

现在，对于每个 i 我们要求包含它且右端点小于 lst_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)$。