考察
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.
出典