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

[問題案] Range Chmin Chmax Add Range Sum (range_chmin_chmax_add_range_sum) #243

Closed
kmyk opened this issue Dec 31, 2019 · 5 comments · Fixed by #257
Closed

[問題案] Range Chmin Chmax Add Range Sum (range_chmin_chmax_add_range_sum) #243

kmyk opened this issue Dec 31, 2019 · 5 comments · Fixed by #257

Comments

@kmyk
Copy link
Contributor

@kmyk kmyk commented Dec 31, 2019

(任意) 問題ID: {ID}
問題名: {名前}

問題概要

ぜんぶのせ segment tree beats です (参考: https://tjkendev.github.io/procon-library/cpp/range_query/segment_tree_beats_2.html )

長さNの整数列a_0, a_1, ..., a_{N - 1}が与えられる。Q個のクエリを処理

  • 0 l r b: a_l, ..., a_r-1それぞれについて、a_i = min(a_i, b) をする
  • 1 l r b: a_l, ..., a_r-1それぞれについて、a_i = max(a_i, b) をする
  • 2 l r b: a_l, ..., a_r-1それぞれについて、a_i = a_i + b をする
  • 3 l, r: a_l ~ a_r-1の総和を出力

入力

出力

制約

  • 1≤N,Q≤500,000

メモ

  • 問題IDこれでいい?
  • Range Update は Range Chmin + Range Chmax で済むので省略
  • Range Min (取得) や Range Max (取得) はふつうのセグ木でもできるので省略
  • Range Chmin Range Sum だけの問題もついでに作るとよい気がしています。(ところでクエリの種類を 0, 1, 2, 3 でなく chmin chmax add sum とかにすればクエリが増減してもコードを使いまわせてうれしいかもしれない)
@kmyk

This comment has been minimized.

Copy link
Contributor Author

@kmyk kmyk commented Dec 31, 2019

全てmod 998244353

mod はいらないでしょ、修正

@yosupo06

This comment has been minimized.

Copy link
Owner

@yosupo06 yosupo06 commented Dec 31, 2019

提案ありがとうございます!

  • 問題IDこれでいい?

はい いいと思います(Range Chmin Range Chmax Range Add Range Sumでも詠唱感(?)があって楽しいですが)

  • 実は値を10^9にするとlong longに収まらないという要素があります(値をAとして QNA + o(QNA))

値を10^6にするかsumでmodを取るかのどちらかだと思います。値を10^6にするのを推します(一部だけmodが入ると違和感がある)

@yosupo06

This comment has been minimized.

Copy link
Owner

@yosupo06 yosupo06 commented Dec 31, 2019

chmin, chmaxの値をどうするかという話があり、ムズいな

@kmyk

This comment has been minimized.

Copy link
Contributor Author

@kmyk kmyk commented Dec 31, 2019

add によって値が 5 * 10^11 ぐらいになるのに chmin, chmax は 10^6 までなのはおかしいという話ですか?
選択肢は以下の 3 つぐらいしかないはず。(3.) がきれいかなと思いますがどうでしょうか

  1. verify の用途には十分だし気にしない
  2. add クエリは b ≤ 10^4 にして chmin, chmax クエリは b ≤ 10^8 にするなど
  3. 「各時点において数列の要素は常に 10^12 より小さい」みたいな制約を足すして全部 10^12 とかでやる
@yosupo06

This comment has been minimized.

Copy link
Owner

@yosupo06 yosupo06 commented Dec 31, 2019

はい、その通りでなんとなく値の値域?次元?みたいなのが揃ってないとやだと言う感覚があります(もちろんverifyには十分ですが…)

私も3がいいと思います checkerの手間が増えますけど許容範囲でしょう(既にもっとすごい問題がありますし)

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.