コンテスト後の議論で多く見られた別解を紹介します。(参考 https://twitter.com/PCTprobability/status/1644703446619287555 )

\(\mathrm{dp}_i\) 末尾の値が \(i\) であるような狭義単調増加部分列の長さの最大値 とします。\(l_i,\ldots,r_i\) は(狭義単調増加部分列として選ばれる場合は) \(r_i\) まで選ばれるものとして良いため、上記 \(\mathrm{dp}\) の添え字として考えられる値は \(r_i\) に限ってよく、座標圧縮が出来ます。

遷移は、遷移元の値が \(l_i\) 未満の場合は \(l_i,\ldots,r_i\) が追加されるため長さが \(r_i-l_i+1\) 増えます。一方、遷移元の値が \(l_i\) 以上 \(r_i\) 以下の場合(この値を \(x\) とします)、\(x+1,x+2,\ldots,r_i\) が追加されるため \(r_i - x\) だけ増えます。これを実現するには各 \(i\) に対して \(\mathrm{dp}_i\) と \(\mathrm{dp}_i - i\) を区間 \(\max\) のセグ木で管理すればよく、全体で \(\mathrm{O}(N \log N)\) で正解できます。