ABC 401-500/ABC421F - Erase between X and Y - 競技プログラミング用 知識集積所

---

問題

ABC421F

必要知識

B以下レベルの内容は省略

• 隣接リスト※
• 逆写像※
• Fenwick木※

別解の方法で解く場合

• 連結リスト※

考え方

途中で更新がある総和クエリといえばFenwick木※の出番。
問題は、Fenwick木※では途中に挿入ということができない点。
これをどうクリアするかがポイントとなる。

挿入するときの困難は、値を後ろに1つずつずらすのが難しい点にある。
そこで、後から値を挿入する予定がある場所に0を用意しておき、挿入のかわりに値の更新で済ませるようにすればよい。
つまり、削除がなかった場合に最終的にできる数列をクエリ先読みで求めておき、挿入の時には規定位置の値を更新するようにすればよい。

最終的にできる数列は、以下の手順で求められる。

• 隣接リスト※で、クエリ1で何の次に何を入れるかの有向非巡回グラフ※を作っておく
• 空のvectorを用意する
• deque※を用意し、0を入れておく
• deque※が空になるまで以下のループ
  • deque※の先頭を取り出し、vectorの末尾に追加する
  • その値の後ろに挿入することになる値を、小さい順にdeque※に前から挿入する

これの逆写像※を用意しておくことで、事前準備は終わり。

クエリの処理は、以下。

• タイプ1の場合、用意した逆写像※を見て、Fenwick木※の該当位置の値を更新する
• タイプ2の場合、以下の2つをやる
  • xとyの規定位置を見て、その間の合計を求めて出力
  • その合計を、和を取った区間の適当な位置から引いておく

タイプ2の後半の処理は、和をとった区間全てを0に戻す代わりである。
一度和を取るのに使われた区間は、以後「そこには関連しない区間」「そこをまるごとまたぐ区間」しか来ないことが保証されているため、まとめて1点から引くことで代替可能となっている。

解答例

解答例

注意点

答えがint型に入らない場合がある

全部ずらっと並べた上で一気に和を取ると、2*10^9を超える場合がある。
long long型を使うこと。

別解

連結リスト※を使う

公式解説にある方法。
連結リスト※で、常に「自分の後ろにいるのは誰か」を全員分管理するようにする。
すると、xとyのうち前にいる方から、連結リスト※を辿ることで区間和を求めることができ、xの後ろを直接yに変更すれば削除も一瞬。

ただし、1つ大きな問題がある。
それは、xとyの値のどちらが前にいるかがわからないこと。
単純にそれぞれから調査をすると、リスト系の弱点がモロに影響し、先に調査した方が長くてハズレだと時間のロスが大きい。
そこで、両方から同時に調査をしてハズレを引くリスクを最小限にしておく。
当たりまでの距離が長い場合もあるが、その場合は大量削除されることになるので総計での時間ロスはあまり膨らまない。

解答例