CS Academy Consecutive Subsequence

リンク : https://csacademy.com/contest/archive/task/consecutive-subsequence/

問題概要

長さNの数列が与えられる。一つの任意の数字を任意の場所に入れられるとする。昇順に連続した最長の部分数列の長さを求めよ。(部分数列は連続している必要はない)

解説

i番目の数列をA_iとする。dp[i][j] : i番目を使う、最長の長さとし、jが1ならすでに文字を挿入し、0ならまだ挿入していないとおく。もし、A_i+1の値であるiより大きいindexが複数あるなら一番小さいものを選ぶ。ここから、v[i][j] : iの数字である前からj番目のindexとすると、O(log n)でA_i+1の値であるiより大きいindexの最小が求められる。A_i+1であるiより大きい最小のindexをnex1、A_i+2であるiより大きい最小のindexをnex2とすると、dpの遷移は
dp[nex1][0]=max(dp[nex1][0],dp[i][0]+1);
dp[nex2][1]=max(dp[nex2][1],dp[i][0]+1);
dp[nex1][1]=max(dp[nex1][1],dp[i][1]+1);
となる。

LL n, k, ans, A[110000];
vector<LL>v[1100000];
LL dp[110000][2];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> A[i];
        v[A[i]].push_back(i);
    }
    rep(i, 1100000)v[i].push_back(n);
    rep(i, n) {
        LL nex1 = v[A[i] + 1][upper_bound(v[A[i] + 1].begin(), v[A[i] + 1].end(), i) - v[A[i] + 1].begin()],
            nex2 = v[A[i] + 2][upper_bound(v[A[i] + 2].begin(), v[A[i] + 2].end(), i) - v[A[i] + 2].begin()];
        dp[nex1][0] = max(dp[nex1][0], dp[i][0] + 1);
        dp[nex2][1] = max(dp[nex2][1], dp[i][0] + 2);
        dp[nex1][1] = max(dp[nex1][1], dp[i][1] + 1);
    }
    cout << dp[n][1]<<endl;
    return 0;
}