LISum [Ritsumeikan University Competitive Programming Camp 2019 Day 1 E]

https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp19Day1/problems/E

前提知識

• LIS

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#RitsCamp19Day1/3418982

LISをセグメントツリーで解く場合は、
st[i] := 最後の数がiとなる増加列の最長の長さ
を更新して、解いていく。
　
これが理解できていれば、これを拡張すればすぐ解ける。
st[i] := 最後の数がiとなる増加列で{最長の長さ, 最長での最大総和}
このように拡張して更新する。

int N, A[101010];
SegTree<pair<int,ll>, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

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

        p.first++;
        p.second += A[i];

        chmax(p, st[A[i]]);
        st.update(A[i], p);
    }

    cout << st.get(0, 1 << 17).second << endl;
}