solution

LIS。 修正する区間$[l, r)$の右端$r = n$かつ修正する量$d = x$としてよい。 普通の$O(n \log n)$ LISのアルゴリズムの配列を2本持って上手くやる。 単純には$i$番目まで見て状態が\(j \in \{ (+d\text{してない}), (+d\text{してる間}), (+d\text{して止めた後}) \}\)のどれであるかから列の長さを$\mathrm{dp}(i, j)$としてDPしたいが、これと$O(n \log n)$ LISを上手く融合させる感じになる。 $O(n \log n)$。

修正の方法について。 $d \ge 0$とすると、$+d$を$l$で始めた後に$r$で取り止めると損をするだけで、かつ増やすならできるだけたくさん増やした方が得。 $d \le 0$の場合も同様だが、前半に$-x$するのは後半に$+x$するのと変わらない。 よって区間$[l, n)$に$+x$する場合だけ考えればよい。

普通の$O(n \log n)$ LISの過程で現われる配列を考え、これを2本持つ。 「長さ$j$の増加列を作ったときの末尾の要素の最小値」が配列$l$の$j$項目となる。 1本目$l_0$はそのままのもの、2本目$l_1$は全体$[0, n)$に$+x$した列に対するもの。 それぞれ伸ばしながら、都度1本目から2本目に切り替えるような処理をしてやる。 そのまま伸ばす操作のために $l_0, l_1$に$t_i, t_i + x$をそれぞれ付け加えた後に、$+ x$する境界の処理のために各点で \(l_1 \gets \max \{ l_0, l_1 \}\) の処理をする。 後者をまったくそのままやると$O(n)$だが、必要な箇所だけ修正するようにすると$O(1)$であり、全体でも$O(n \log n)$。

note

解法の説明が難しい。 正しいことは分かるけど不安。 この回のコンテストの問題の中で一番「直感」みたいなのを要求する気がする。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using ll = long long;
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

int push(vector<ll> & l, ll x) {
    auto it = lower_bound(l.begin(), l.end(), x);
    if (it == l.end()) {
        l.push_back(x);
        return l.size() - 1;
    } else {
        *it = x;
        return it - l.begin();
    }
}

int solve(int n, ll x, vector<ll> const & t) {
    vector<ll> l0, l1;
    for (ll t_i : t) {
        push(l1, t_i + x);
        int j = push(l0, t_i);

        // l1 = max(l0, l1)
        while (l1.size() <= j) {
            l1.push_back(l0[l1.size()]);
        }
        chmax(l1[j], l0[j]);
    }
    return l1.size();
}

int main() {
    int n; ll x; cin >> n >> x;
    vector<ll> t(n);
    REP (i, n) cin >> t[i];
    cout << solve(n, x, t) << endl;
    return 0;
}