説明を簡便にするために \(A_i\) は全て異なるとします。これは

• \(A_i := NA_i + i\)
• \(X := NX\)
• \(Y := NY\)

などの前処理を行えばよいです。

例えば、 dp[i][l][a][s] = 最初i個の要素のsubsequenceであり、長さがl、最後の要素がa、次に足す値がs以上でないといけない などのDPで多項式時間で解くことはできます。

先述のDPは言い換えると、タプル \((l, a, s)\) の集合を保持しながら、後ろに要素を \(1\) つずつ足していく、と考えることが出来ます。しかしタプルの要素は全て保持するには多すぎます。

ここで、\(2\) つの状態 \((l, a, s), (l', b, t)\) が、\(l \ge l'\), \(a \le b\), \(s \le t\) を満たすとき、明らかに後者の状態を捨ててよいです。実はこれで捨てられない極大なタプルは高々 \(N + 1\) 個しか存在しない、というのがこの問題の本質です。

より強く、\(2\) つの状態 \((l, a, s), (l', b, t)\) が、\(l \ge l'\), \(a \lt b\) を満たすとき、\((l', b, t)\) を捨ててよいことが示せます。

• \(s \le t\) ならば明らかである
• 数列で \(a\) が \(b\) の前に出てくるとき、\((l, a, s)\) に \(b\) を足すことでより良い状態を作れる
• 数列で \(b\) が \(a\) の前に出てくるとき、\((l', b, t)\) に \(a\) を足すことでより良い状態を作れる

これで不要な要素を消し続けることで、状態は以下の条件を満たすタプル列 \((l_1, a_1, s_1), (l_2, a_2, s_2), \cdots, (l_m, a_m, s_m)\) まで圧縮できます。

• \(l_i\) は単調増加
• \((a_i, s_i)\) は辞書順で単調増加 (\(a_i\) は distinctとは限りません)

あとはこのタプル列を適切なデータ構造、例えば \(l_i\) を index として \((a_i, s_i)\) を値として持つ segment tree で管理し、高速に状態の更新をすればよいです。

適切に実装を行うと、操作回数を (タプル列の要素数) + (\(a_i\) の種類数) をポテンシャルとして \(O(N)\) 回と評価できます。よって計算量は \(O(N \log N)\) となります。

writer解 は実は不要なタプルを完全に消さなくてよいなどの考察を加え、実装を簡略化しています