思路总览

给定是一个 $1\sim n$ 的排列。设全局最长上升子序列（LIS）长度为 $L$。 对每个位置 $i$，我们只需统计：有多少条 LIS 会“经过”元素 $a_i$。

经典分解法：

• 令 Lend[i]：以位置 i 结尾的最长上升子序列长度；
• 令 CntL[i]：达到 Lend[i] 的方案数；
• 令 Rbeg[i]：从位置 i 开始（包含 i）的最长上升子序列长度（向右）；

题目内容

给定一个长为$n$ 的排列 {$a$}。排列是指，{$a$} 包含$1$~$n$中的所有元素恰好一次。

回顾一下，{$a$} 的一个子序列是指从{$a$}中将若干元素(不一定连续)提取出来而不改变相对位置形成 的序列。 对于 {$a$} 的一个子序列 {$b$}，如果 {$b$} 中的元素单调递增，就称{$b$}是{$a$}的一个上升子序列。