Suddenly, A Tempest 2

$M$回行われる座標をズラす操作のことを単に「操作」、$Q$ 回問われるクエリのことを単に「クエリ」と言います。

まず、操作によって各点のX座標は変化しません。よって、点をX座標に関してソートしたときに、操作 x a は、

• ソートした配列において、X座標が $x$ 未満の部分の $y$ 座標を $-a$ し、X座標が $x$ 以上の部分の $y$ 座標を $+a$ する

と言い換えることが出来ます。この加算は、あるインデックスを境にして、それ以前の範囲に $-a$ を加算、それ以降の範囲に $+a$ を加算することで可能です。 このインデックスの位置に関しては二分探索を使って求めることができ、この範囲加算はいもす法を用いることで可能です。

計算量は、

• 点をソートするのに $O(\log N)$

「二分探索」や「いもす法」について知らない場合は、以下のような資料、または「鉄則本」といわれる本を見てみましょう

二分探索

• lower_boundに関するc++リファレンス：https://cpprefjp.github.io/reference/algorithm/lower_bound.html
• めぐる式二分探索：https://qiita.com/drken/items/97e37dd6143e33a64c8c
• (Python向け) bisectライブラリの使い方 ：https://output-zakki.com/python_biesct/

  • Pythonには、lower_bound に対応するものとして bisect_left, uppper_bound に対応するものとして bisect_right が存在します。返り値の仕様はイテレータかインデックスか違いでしかないのでほぼ同様に使えます。

いもす法

• いもす法について：https://imoz.jp/algorithms/imos_method.html

Bouns： この問題では、$M$ 回の操作の後に $Q$ 回のクエリがありましたが、「操作」と「クエリ」がランダムに交互に来る場合でも解答することが出来ます。 気になる人は、「遅延セグ木」や「双対セグ木」という言葉で検索してみてください。

解答例(c++)

https://mojacoder.app/users/n_bitand_n_per_3/problems/Suddenly_A_Tempest_2/submissions/84977536-8c61-48e9-99e2-c9ac0db621de