Sequence Decomposing [AtCoder Beginner Contest 134 E]

https://atcoder.jp/contests/abc134/tasks/abc134_e

前提知識

• 2Dセグメントツリー、セグメントツリーにセグメントツリーを載せるテク ← 公式解法ではいらない

解説

https://atcoder.jp/contests/abc134/submissions/6479037

先頭から貪欲に増加列を作っていき、何周で全部空にできるかという問題になる。
先頭から貪欲に作っていくので、

• cu番目より後
• A[cu]より大きい
• 上の2つの条件を満たす中で、最もcu番目に近い

を高速に取得できるデータ構造が要求される。
これは2Dセグメントツリー、セグメントツリーにセグメントツリーを載せるテクで作ったデータ構造を作れば実現できる。
N=10⁵が最大なので、たぶん大丈夫だろうと投げたら通る。
O(NlogNlogN)

int N, A[101010], vis[101010];
Healthy2DSegTreeVer2 st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    vector<vector<int>> idx(N);
    rep(i, 0, N) idx[i].push_back(A[i]);
    st.init(idx);
    rep(i, 0, N) st.update(i, A[i], i);

    int ans = 0;
    rep(i, 0, N) if (!vis[i]) {
        ans++;
        int cu = i;
        while (cu < N) {
            vis[cu] = 1;
            st.update(cu, A[cu], inf);

            cu = st.get(cu + 1, N, A[cu] + 1, inf);
        }
    }

    cout << ans << endl;
}