ABC 324 G — Generate Arrays

考察

全sequenceは元permutation Aの部分列なので、各elementは一意な(original position,value)を持ち、sequence内順序はoriginal position順のままである。

各splitで2つに分かれるうち短い側だけのelementを別containerへ移し、長い側には既存containerを割り当てれば、1 queryの移動数をmin(両length)にできる。

position splitとvalue splitの両方を扱うには、各sequenceで(position,value)をposition順とvalue順の2つのbalanced setに同期保持すればよい。

採用する候補: sequenceごとにposition順・value順の2 setを持ち、短いresult側だけを移すreverse small-to-large simulation。

各elementの移動回数を逆向きmergeの倍増論法でlog N回に抑え、両種類のsplitを同じ枠組みで処理できる。

棄却する候補: 各operationで新sequenceに属する全elementを常にsourceからコピー・削除する。

毎回大きい側が新sequenceになるcaseを繰り返すと同じ多数要素を何度も走査してNQ規模になる。

棄却する候補: 各sequenceをvectorとして保持し、type 2で全要素をvalue比較する。

value thresholdがposition上で連続とは限らず、長いsequence全scanを避けられない。

type 1ではprefix長min(x,L)とsuffix長L-min(x,L)が既知で、短い方をposition setの端から列挙できる。

type 2ではvalue x以下とx超のsizeをorder-statisticまたは中央値管理で判定し、短い方をvalue setの端から列挙できる。

短い側が元sequence sに残る場合はcontainer handleを交換し、既存の大containerを新sequence iへ割り当てることで、仕様上のIDを保ったまま移動量を小さくする。

各sequence handleにposition-ordered setとvalue-ordered setを持ち、element移動時は両方からeraseして相手containerへinsertする。type 1はcut=min(x,length)からprefix/suffixの小さい側をposition端から移す。type 2はvalue rankで≤x側と>x側のsizeを得て、小さい側をvalue端から移す。移動した側・残った側が仕様のs,iへ対応するようhandleを必要ならswapし、新sequence iのsizeを出力する。

典型の発動条件

reverse small-to-large

発動条件: partition操作列で毎回2集合のどちらかを新containerへ分離できるとき。

短い側だけを動かし、逆時間では小集合を大集合へmergeする倍増解析を使う。

複数key indexの同期管理

発動条件: 同じ要素集合を位置thresholdと値thresholdの両方で分割するとき。

position setとvalue setを同時更新する。

container handle swap

発動条件: logical IDが要求する側と、物理的に残したい大container側が逆になるとき。

pointer/handleだけ交換し、大量要素の移動を避ける。

問題固有の要素

split後も各要素は1つのsequenceにだけ属し、逆順に見ると必ず2集合のmergeになるため、通常のsmall-to-largeを時間反転したamortized解析が成立する。

別の問題へ持ち帰る視点: 分割操作が多い問題では逆時間のmergeとして見て、短いresultだけを物理移動する設計を検討する。

正当性

位置による切断も値による切断も、二集合が元の列を過不足なく分割する。短い側だけ移しても、必要なら容器の担当IDを交換することで仕様どおりの二列を得る。各移動で要素の所属容器が半分以下になるため、移動回数も対数回に限られる。

実装上の注意

  • type 1のx≥lengthはnewが空、x=0はsourceが空になる境界でもhandle割当を正しく行う。
  • element移動はposition/value両setへ必ず同じ1要素を反映し、sequence sizeの不整合を防ぐ。
  • type 2でvalue xが存在しない場合もupper_bound境界から≤xと>xを正しく分ける。

復習の核

  • 短い側がsourceに残るcaseでhandle swap後のsequence IDを追い、同じelementがposition/value setの両方で同じcontainerへ所属するか確認する。

計算量と制約

時間

O(N log²N+Q log N)、各要素は小さい側分割のたび所属sizeが半減し移動O(log N)回。

空間

O(N+Q)、二順序setとhandle。

制約との対応

公式制約の確認範囲: Time limit: 6 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq2\times10^5; 1\leq A _ i\leq N\ (1\leq i\leq N); A _ i\neq A _ j\ (1\leq i\lt j\leq N); 1\leq Q\leq2\times10^5; t _ i=1,2\ (1\leq i\leq Q); 0\leq s _ i\lt i\ (1\leq i\leq Q); 0\leq x _ i\leq N\ (1\leq i\leq Q); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Generate Arrays の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: small-to-large・DSU on Tree

主題
  • small-to-large・DSU on Tree: 小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: small-to-large・DSU on Tree

    補助タグ: ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: small-to-large・DSU on Tree

    • 小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題