https://kanpurin.hatenablog.com/entry/2020/10/04/153401

問題概要

長さ ${N}$ の数列 ${A}$ の最長増加部分列は何通りあるか求めよ.

${1\leq N\leq 2×10^5\\ -10^9\leq A_i\leq 10^9}$

すぐ思いつくのが ${dp[i]=}$ 最後に ${A_i}$ をとったときの ${i}$ 番目まででのLISの取り出し方の総数, としたDP

サンプル1(1 4 2 5 3)だと ${dp=\{1,1,1,2,1\}}$ みたいになる.

このDPの更新式は, ${l_i=}$ 最後に ${A_i}$ をとったときの ${i}$ 番目まででのLIS長として,

$dp[i]=\sum_{j < i,A_j < A_i,l_j+1=l_i}dp[j]$

となる. ${l_j+1=l_i}$ の条件がなければ, BITを用いて ${A_i}$ の小さい方から見ていくいつものやつで解ける.

${l_j+1=l_i}$ の条件があっても同様に ${l_i}$ の値ごとにBITを作成して, ${dp[i]}$ の更新の際に ${l_i-1}$ のBITを参照すればよい. BITのサイズの和は ${O(N)}$ であるので計算量も大丈夫.

典型知識から思いつく自然な解法で解けた. 他の解法見てたら短く書けるっぽいが, 自然な流れ重視で書いた.