ABC 344 E — Insert or Erase

考察

queryは既知の値xの直後挿入またはx自身の削除であり、位置indexによるrandom accessは不要である。各valueから前後valueへ直接辿れるようにすれば、変更箇所は常に定数本のlinkだけになる。

採用する候補: valueをnode keyとするdoubly linked listをhash mapで実装する

棄却する候補: vectorの途中へinsert/eraseする

後続要素のshiftが一query O(|A|)となり、合計二乗時間になり得る。

各valueに(prev,next)を持つ連想配列を作り、head/tail sentinelも接続する。type 1はxとそのnextの間へy nodeを挿入し、type 2はxの両隣を直結してmapからxを消す。最後にhead.nextからtailまでnextを辿り出力する。

典型の発動条件

doubly linked list

発動条件: 既知node位置での挿入・削除を頻繁に行い、最後に順序走査したい。

prev/next双方を持ち、局所linkの張替えだけで操作する。

key-to-node indexing

発動条件: 操作対象が位置でなく一意なvalueで指定される。

hash mapでvalueからlink情報へ直接accessし、linear searchを避ける。

問題固有の要素

通常のlist iteratorを保存する代わりに、値が全て一意という条件を利用してprev/nextをvalue同士のmapとして直接表せる。

別の問題へ持ち帰る視点: 一意key指定のlinked sequenceはnode objectなしでもkey→neighbor mapsで実装できる。

正当性

distinct value保証によりvalue自身をnode identityとして使える。xの直後y挿入ではy.prev=x,y.next=x.nextとし両隣を繋ぎ直し、x削除ではx.prev.next=x.nextとx.next.prev=x.prevだけを更新すれば順序不変条件が保たれる。 xのnodeをO(1)期待で特定し、挿入・削除を前後pointerの定数更新で処理できる。

実装上の注意

  • 先頭・末尾削除をsentinelで統一し、挿入時は旧nextを保存してから4本のlinkを更新する。削除済みnode情報を後のlookupに残さない。

復習の核

  • head/tail削除、末尾挿入、挿入直後の削除、長さ1を保つ操作列でlinkの双方向整合性を検査する。

計算量と制約

時間

hash map版は期待O(N+Q)、平衡木版はO((N+Q)log(N+Q))。

空間

O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2\times 10^5; 1 \leq Q \leq 2\times 10^5; 1 \leq A_i \leq 10^9; A_i \neq A_j; For queries of the first type, 1 \leq x,y \leq 10^9.; When a query of the first type is given, x exists in A.; For queries of the second type, 1 \leq x \leq 10^9.; When a query of the second type is given, x exists in A.; After processing each query, A is not empty, and its elements are distinct.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Insert or Erase の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 要素索引と連結リストで局所linkを更新する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 索引付き連結リスト

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

      学習の位置

      体系上の位置: 要素索引と連結リストで局所linkを更新する

      • 要素IDから前後linkを引き、挿入・削除で変わる局所linkだけを更新して列順を復元できる。

      この解説で扱わないこと:

      • 全候補の大小順や区間集約を保つ平衡木・heap。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題