23JOIG春合宿1-1 - Rocket Launching

問題リンク: https://atcoder.jp/contests/joigsp2023/tasks/joigsp2023_a

$${A, B}$$を整数からなる多重集合とします。突然ですが、次のクエリをオンラインで処理することを考えます（$${x, h, t}$$はクエリで与えられます）。

• クエリ 1 : $${A}$$に$${x}$$を追加する。

• クエリ 2 : $${A}$$から$${x}$$を削除し、$${B}$$に$${h}$$を追加する。ただし、$${x\in A}$$が保証される。

• クエリ 3 : $${\max(t-\min A, \max B)}$$を返答する。

$${(X_i, 1, i), (X_i+H_i, 2, i), (T_j, 3, j)\ (1\le i\le N, 1\le j\le Q)}$$をすべて含んだ配列を辞書順にソートします。この配列を先頭から走査して、

• 2 番目の要素が 1 ならば、$${x=X_i}$$としてクエリ 1 を処理する。

• 2 番目の要素が 2 ならば、$${x=X_i, h=H_i}$$としてクエリ 2 を処理する。

• 2 番目の要素が 3 ならば、$${t=T_j}$$としてクエリを処理する。特に、返答は$${j}$$行目に出力すべき値となる。

提出コード: https://atcoder.jp/contests/joigsp2023/submissions/49234897

おきもち

$${j}$$行目に出力する値は$${f(t, i)}$$の最大値です。ここで、$${f(t, i)}$$は次の条件をすべて満たす関数です。

• $${t\in (-\infty, X_i)\implies f(t, i) = 0}$$

• $${t\in [X_i, X_i+H_i]\implies f(t, i) = t-X_i}$$

• $${t\in (X_i+H_i, \infty)\implies f(t, i) = H_i}$$

なので$${t\in [X_i, X_i+H_i]}$$となるような$${X_i}$$の最小値と、$${t\in (X_i+H_i, \infty)}$$となるような$${H_i}$$の最大値が分かるとうれしいです。適当な考察を重ねると$${X_i, X_i+H_i, T_j}$$でイベントソートをしたくなります。