ABC 393 F — Prefix LIS Query

考察

増加部分列では末尾が最大の要素になる。そのため、各長さについて「末尾をどこまで小さくできるか」が分かれば、値の上限を満たすかも判定できる。質問ごとに要素を除いてLISを求め直す代わりに、この最小末尾を共有することを考える。

質問で使うのは先頭からの区間(prefix)なので、右端が短い質問から処理すれば、配列の要素を一つずつ追加するだけでよい。各質問でLISを再計算すると最悪 O(NQlog⁡N)O(NQ\log N) かかるが、同じprefixまでの計算を使い回せる。

元の配列の添字は 1,…,N1,\dots,N とする。先頭の RR 要素を処理した時点で、動的配列 tails を次の意味で持つ。

  • tails の添字は0始まりで、tails[j] は長さ j+1j+1 の狭義単調増加部分列の最小末尾である。
  • 存在する長さの分だけ要素を持つ。空のprefixでは tails も空で、現在のLIS長は tails.size() に等しい。
  • 長さが増えるほど最小末尾も狭義に増加するため、tails は二分探索できる。

新しい値 AiA_i を追加するときは、lower_bound(tails, A_i)、すなわち AiA_i 以上の最初の要素の位置 pp を探す。その位置があれば tails[p] を AiA_i に置き換え、末尾の次なら追加する。等しい値も置き換えるので、同じ値を二度選んで長さを増やすことはない。

例えば A=(2,2,3)A=(2,2,3) なら、更新は次のようになる。

右端 RRtails更新の意味
1(2)2を追加し、長さ1に
2(2)同じ2を置換し、長さは1のまま
3(2,3)3を追加し、長さ2に

では、値の上限 XX を持つ質問にはどう答えるか。長さ j+1j+1 の部分列で全要素を XX 以下にできる条件は、tails[j] が XX 以下であることだ。最小末尾自体が XX 以下なら、その末尾を実現する増加部分列の全要素も上限を満たす。

tails は増加しているので、XX 以下の要素は先頭に連続して並ぶ。その個数を kk とすると、対応する長さは 1,…,k1,\dots,k であり、最大長も kk となる。upper_bound(tails, X) が返す「XX より大きい最初の位置」は、この個数 kk そのものである。最後に条件を満たす添字に1を足す代わりに、条件を満たす要素の個数を直接読むと考えると、添字と長さを混同しにくい。

先ほどの例では、R=2R=2 の tails=(2) で X=2X=2 の答えは1。R=3R=3 の tails=(2,3) では、X=2X=2 なら位置1、X=3X=3 なら末尾の次の位置2が返り、答えはそれぞれ1、2になる。更新の lower_bound と質問の upper_bound は、等しい値の扱いが異なる。

具体的には、質問を右端 RR ごとのbucketへ入れ、値上限 XX と入力時の質問番号を保存する。tails を空で初期化し、i=1,…,Ni=1,\dots,N の順に次を行う。

  1. AiA_i を lower_bound で tails に反映する。
  2. R=iR=i の質問すべてに、upper_bound(tails, X) の0始まりの位置を答える。
  3. 答えを元の質問番号の場所へ保存する。

最後に答えの配列を入力順に出力する。同じ右端を持つ質問はすべて、AiA_i を含む同じ状態で処理する。

典型の発動条件

offline prefix query

質問を入力順に処理する必要がなく、先頭からの区間の状態を一要素ずつ更新できるときに使う。右端ごとのbucketで処理すれば、質問のソートも不要になる。入力時の質問番号を持って答えの順序を戻す。

LIS tails invariant

同じ長さの増加部分列なら、末尾が小さいほど将来の値をつなげやすい。長さ別の最小末尾だけを残し、狭義増加では lower_bound で更新する。その状態が値上限にも答えられるかは、末尾と部分列全体の値の関係から確認する。

問題固有の要素

「全要素が XX 以下」という条件も、増加部分列では末尾一つで判定できる。値上限をDPの新しい次元にせず、最小末尾列の中で条件を満たす長さを二分探索すればよい。

別の問題へ持ち帰る視点は、標準のDPが保持する最適値から、追加された質問条件を直接判定できないかを調べることだ。

正当性

tails[j] を長さ j+1j+1 の増加部分列の最小末尾とする。長さ j+2j+2 の部分列から末尾を除くと、その末尾より小さい値で終わる長さ j+1j+1 の部分列が得られるため、最小末尾も長さとともに狭義に増加する。

空のprefixでは不変条件を満たす。新しい値 aa の lower_bound の位置を pp とすると、p>0p>0 なら tails[p-1] は aa より小さく、それを実現する長さ pp の部分列に aa をつなげられる。p=0p=0 なら aa 単独を選べる。いずれも長さ p+1p+1 の末尾を aa にできる。より短い長さの最小末尾はすでに aa より小さいので改善せず、より長い部分列を aa で終えるには、更新前に長さ p+1p+1 以上で末尾が aa 未満の部分列が必要だが、それは pp の定義に反する。従って位置 pp の置換または末尾への追加だけで不変条件を保つ。

値上限 XX を満たす長さ j+1j+1 の増加部分列が存在すれば、その末尾以下である tails[j] も XX 以下である。逆に tails[j] が XX 以下なら、その最小末尾を実現する部分列の全要素が XX 以下になる。従って実現可能な長さは、tails の中の XX 以下の要素数を kk として 1,…,k1,\dots,k であり、答えは kk である。upper_bound の0始まりの位置はこの個数に等しい。各質問をちょうど先頭の RR 要素を反映した直後に処理するので、求めるprefixに対する正しい答えを返す。

実装上の注意

  • tails は0始まりの動的配列とし、未到達の長さや番兵は入れない。更新位置が tails.size() なら追加し、それ以外なら置換する。
  • 狭義増加の更新には、同値を置き換える lower_bound を使う。質問は上限と等しい値も許すので upper_bound を使う。C++なら upper_bound(tails.begin(), tails.end(), X) - tails.begin() が答えであり、1を足したり引いたりしない。
  • R=iR=i の質問には AiA_i の更新後に答える。特に R=1R=1 や、最後の要素を選んで答えが伸びる質問で処理順の誤りが現れる。
  • 質問の処理順は右端の順へ変わるため、答えは元の質問番号で保存する。

復習の核

  • 長さ別の最小末尾は、将来の延長だけでなく「全要素が上限以下か」の判定にも使える。
  • tails[j] は長さ j+1j+1。答えは最後の添字ではなく、上限以下の末尾の個数で読む。
  • 同値を伸ばさない更新は lower_bound、同値を含めて数える質問は upper_bound。

計算量と制約

時間

NN 要素、QQ 質問。bucketの準備と出力は O(N+Q)O(N+Q)、各要素の更新と各質問の二分探索はそれぞれ O(log⁡N)O(\log N) なので、全体は O((N+Q)log⁡N)O((N+Q)\log N)。質問をソートする方法では別途 O(Qlog⁡Q)O(Q\log Q) が必要になる。

空間

tails と元の配列に O(N)O(N)、bucketと答えの配列に O(N+Q)O(N+Q) を使い、全体は O(N+Q)O(N+Q)。

制約との対応

1≤N,Q≤2×1051\leq N,Q\leq 2\times 10^5、1≤Ai≤1091\leq A_i\leq 10^9 なので、質問ごとの再計算を避け、一要素・一質問あたり二分探索一回で処理する。1≤Ri≤N1\leq R_i\leq N であり、min⁡{A1,…,ARi}≤Xi≤109\min\{A_1,\dots,A_{R_i}\}\leq X_i\leq 10^9 が保証されるため、公式入力の答えは必ず1以上になる。上限より大きい末尾がなければ、upper_bound は末尾の次を返し、答えは tails.size() になる。制限時間は2秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Prefix LIS Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: LIS・末尾の支配関係

主題
  • LIS・末尾の支配関係: 同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: LIS・末尾の支配関係

    補助タグ: event・値順のオフライン走査

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: LIS・末尾の支配関係

    • 同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。
    • event順にactive集合を更新する — 値・時刻・座標順にeventを並べ、同値eventの処理順を決めてactive集合を増分更新する。逆向き処理や寄与分解とは不変量が異なるため独立に学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題