[問題案] Range Linear Add Range Min

[tko919]

問題名:Range Linear Add Range Min 解法:下側凸包をSegment Treeの形で管理する, $O(\log^2 N)$ per query

問題文

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

• 0 l r b c: $i \in [l,r)$ について $a_i \leftarrow a_i+bi+c$
• 1 l r: $\min_{i \in [l,r)} a_i$ を出力

制約

• $1 \leq N,Q \leq 10^5$
• $|a_i| \leq 10^9$
• $|b|,|c| \leq 10^8$

入力

N Q
a_0 a_1 \ldots a_{N-1}
Query_0
\vdots
Query_{Q-1}

メモ

• $a_i,b,c$ の自然な制約があれば採用したいです

[maspypy]

解法もしかしてこれですか https://judge.yosupo.jp/problem/convex_layers あれば使えることはありそうだし、LC の問題としても良さそうです。

---

制約は，もう少し解法を見ないとちょっと分からないです。x_1y_2-x_2y_1 のタイプの式が出てくると思うけど，$y$ に $Q$ 回 $ai+b$ を足したりすると 2^64 には収まらない感じで考えていますか？

---

別解として、平方分割があると思います。ブロックサイズ $B$ としてブロック内では CHT と思うと、 $O(B+N/B\log N)$。 $O(Q(N\log N)^{0.5})$。（ $b\geq 0$ とかだとこれで 1.5 乗になりそうだけど一般には log がつくか？）。

[tko919]

解法はそれで合ってます。 外積による比較はほぼ必須なので結局「long longの範囲までverifyする」か「__int128_tを使う」かの2択があるのですが、後者はMin Cost b-flow等でも必要になっているのであまり重大な問題ではないと考えました。「常に $a_i \leq 10^{18}$ が成立」程度のものを想定しています。 平方分割も許容するなら $N \leq 50000$ まで制約を落としてもいいかなと思っています。

[maspypy]

なるほど。問題ないと思います、まあわざわざ大きくしなくてもいいのかなという気はしています。制約は https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum これ形式でもよいかもしれません。

$N$ は実装してみて様子見で調整でよいと思います。

[maspypy]

特に 64 bit におさめたりしないでいいということで、今書いてある制約で大丈夫だと思います。