Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[問題案] Segment Add Get Min(segment_add_get_min) #211

Closed
yosupo06 opened this issue Dec 26, 2019 · 4 comments · Fixed by #221
Closed

[問題案] Segment Add Get Min(segment_add_get_min) #211

yosupo06 opened this issue Dec 26, 2019 · 4 comments · Fixed by #221

Comments

@yosupo06
Copy link
Owner

@yosupo06 yosupo06 commented Dec 26, 2019

Add Segment Get Min もほしいです (Li-Chao tree)

Originally posted by @kmyk in #174 (comment)

@kmyk

This comment has been minimized.

Copy link
Contributor

@kmyk kmyk commented Dec 26, 2019

add_line_get_min をちょっと修正するだけだろうし、やっていきたい。仕様は以下でよいですか? @yosupo06


N 本の線分 λ x ∈ [l_i, r_i). a_ix + b_i が存在します。 Q 個のクエリを処理してください。

  • 0 l r a b: 線分 λ x ∈ [l, r). ax + b を追加
  • 1 p: x = p での y 座標の最小を求める。存在しなければ文字列 INFINITY
N Q
l0 r0 a0 b0
l0 r0 a1 b1
:
l{N-1} r{N-1} a{N-1} b{N-1}
que
que
:
que

他は add_line_get_segment と同じ


確認するべき点:

  1. 最初に N 本与えられるのは add_line_get_min に揃えておた方がよさそう。でも解法に無駄にコードが増えるだけだしない方が好みです (宗教戦争)
  2. 区間は左閉右開区間にしてある
  3. 存在しなければ INFINITY はただの面倒要素だけど verify 用としてはほしい。-1 を出力すると衝突するのでだめ。整数でない文字列かあるいは INT64_MAX = 2^63 - 1 だけど、後者は実装依存って感じがよくないので前者にしたい
  4. (後からでも変えれる: 問題文中で線分はどう書けばいいのか。λ x ∈ [l, r). ax + b ではなく f : [l, r) ∋ x ↦ ax + b ∈ ℝ とかの方がよい? 線分という語を陽に使った方が分かりやすいはず。「直線 f を区間 [l, r) 中の各点にのみ追加」みたいな操作的なものは数学的に表示すると何なのかが曖昧になるので避けたい)

(1), (2), (3) はどれも style に書いておきたい

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 27, 2019

  1. 最初に N 本与えられるのは add_line_get_min に揃えておた方がよさそう。でも解法に無駄にコードが増えるだけだしない方が好みです (宗教戦争)

初期化を高速にやるみたいな要素があるなら入れます、例えばsegtreeだとクエリN回投げてO(N log N)で初期化するか、ちゃんとO(N)で初期化するかで結構定数倍が効くことがある

add_(line/segment)_get_min、というかLiChaoTreeにこういう要素があるかなんですが、あるのかな…

  1. 区間は左閉右開区間にしてある

いいと思います

  1. 存在しなければ INFINITY はただの面倒要素だけど verify 用としてはほしい。-1 を出力すると衝突するのでだめ。整数でない文字列かあるいは INT64_MAX = 2^63 - 1 だけど、後者は実装依存って感じがよくないので前者にしたい

文字列出すのでいいと思います。2^63 - 1を出してもサンプルとかわかりにくくなるだけなのでこれはやめましょう

文字列ですが、INFINITYだと将来的にmaxクエリのエラー出したいときとか困る気がするので、None, Nil, Infeasible, No solutionとかそういう感じの方がいいです 個人的にはNone, Infeasibleあたりが好き(後者はあんまり馴染みがない?)

  1. (後からでも変えれる: 問題文中で線分はどう書けばいいのか。λ x ∈ [l, r). ax + b ではなく f : [l, r) ∋ x ↦ ax + b ∈ ℝ とかの方がよい? 線分という語を陽に使った方が分かりやすいはず。「直線 f を区間 [l, r) 中の各点にのみ追加」みたいな操作的なものは数学的に表示すると何なのかが曖昧になるので避けたい)
  • 0 l r a b: 線分 λ x ∈ [l, r). ax + b を追加
  • 1 p: x = p での y 座標の最小を求める。存在しなければ文字列 INFINITY

問題文への要求ですが、「ストーリーなどを極力省く、競プロに親しんだ人がわかる」ぐらいしか要求するつもりはありません(これも書いとくべきですね)。
ですので、私としてはこれで特に問題はないと思います

もちろん↑の制約さえ満たしていれば、どのように書いてくれても大丈夫です。

特にこれにして欲しいという意思表示ではないですが: 私ならというのを一応書いておくと、線分y = ax + bを[l, r)に追加 になると思います(数学的に曖昧とかをあまり気にしないので…)

@kmyk

This comment has been minimized.

Copy link
Contributor

@kmyk kmyk commented Dec 27, 2019

  1. 線分がないときに出す文字列
    Infeasible は「実行不能解」って感じがして今回も問題には違う気がする。
    None は悪くはなさそう (でも Python 感がすこし気になる)。この方向だと No Segment とかもありかも。
    しかしやはり min-monoid の単位元であるところの INFINITY を推したいです。たとえば「長さ N >= 0 の (必ずしも非負でない) 整数の列 A が与えられます。その最小値を求めてください」という問題で N = 0 のときには INFINITY が適切かなと思うためです。
    max クエリがちょっと困るのはそうですが、単に -INFINITY で済むと思っています。

好みの問題だし、ここで決めると後の問題もこれに合わせることになるのでわりと重要な気がしてきました。なので選択は @yosupo06 に任せます。ひとつ指定してください。

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 27, 2019

ではINFINITY

@yosupo06 yosupo06 changed the title [問題案] Add Segment Get Min [問題案] Segment Add Get Min(segment_add_get_min) Dec 28, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

2 participants
You can’t perform that action at this time.