[問題案] Kinetic Tournament

[tko919]

問題名: Kinetic Tournament 解法: https://codeforces.com/blog/entry/82094

問題文

長さ $N$ の整数列 $a0,\ldots,a{N-1}$ と $b0,\ldots,b{N-1}$ が与えられます。 変数 $T=0$ が初期化されています。 $Q$ 個のクエリが飛んできます。処理してください。

• 0 i c d: $a_i \leftarrow c, b_i \leftarrow d $
• 1 l r: $\min_{i \in [l,r)} a_i T+b_i$ を出力
• 2 T_0: $T \leftarrow T_0$ ( $T \leq T_0$ が保証)

制約

• $1 \leq N,Q \leq 10^5$
• 全てのクエリで $0\leq a_i,b_i,T \leq 10^9$

メモ

別のよりよい定式化があれば採用したいです

[maspypy]

beats の一種と思うと jsc2024 の定式化の方が自然な気がしたけど、kinetic tournament という用語に合うのはこの設定っぽいですね。

制約： 負も入れて|a|,|b|,|T|にしてしまった方が変な除算ミスの検出をしてくれそうな気がします bの上限は10^18でいいか‘も

[tko919]

当分ライブラリを作る見込みがないので、持っている別の人が作業しても構いません