最長増加部分列の数え上げ [yukicoder 992]

https://yukicoder.me/problems/no/992

前提知識

• 座標圧縮
• LIS
• セグメントツリー

解説

https://yukicoder.me/submissions/430662

Aに負の数が入っているのは、ちょっと面倒な気がする。
かつ、配列Aは実際の値は特に重要ではなく、数の大小だけが問題なので、座標圧縮して、[0,N)におさめておこう。

LISの解法の、セグメントツリー解法をベースに考えていこう。
先頭から順番に数を見ていきながら、セグメントツリーを更新していく。
具体的には、以下のようにセグメントツリーを作成する。
i番目の要素は、今まで見てきた要素の最後がi=A[j]であるLISの(最長の長さ, その組み合わせ)
これを特殊なマージをしていく。
最長の長さ同士のマージであれば、組み合わせを足してマージする。
そうでないなら、長さが異なるなら、長いほうを利用する。
単位元は(0,1)とすればよい。

これで、更新していき、最終的に全体をgetして、組み合わせ部分を答えると答え。
単位元のマージの仕方と、自身を更新するときにしっかりマージするのに注意。

int N, A[201010];
SegTree<1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    compress1(A, N);

    rep(i, 0, N) {
        auto p = st.get(0, A[i]);
        p.first++;

        auto cu = st[A[i]];
        st.update(A[i], st.comp(cu, p));
    }
    cout << st.get(0, N).second << endl;

}