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 Affine Range Sum(range_affine_range_sum) #233

Closed
yosupo06 opened this issue Dec 29, 2019 · 6 comments
Closed

[問題案] Range Affine Range Sum(range_affine_range_sum) #233

yosupo06 opened this issue Dec 29, 2019 · 6 comments

Comments

@yosupo06
Copy link
Owner

@yosupo06 yosupo06 commented Dec 29, 2019

(任意) 問題ID: range_transform_range_sum
問題名: Range Transform Range Sum

問題概要

遅延伝搬の例を作っておく

1次関数、区間適用、区間sum

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

  • 0 l r c d: a_l, ..., a_r-1それぞれについて、a_i = c * a_i + bをする
  • 1 l, r: a_l ~ a_r-1の総和を出力

全てmod 998244353

入力

出力

制約

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 29, 2019

TransformはAffine Transformationからの着想、もっといいネーミングあるかも?

@kmyk

This comment has been minimized.

Copy link
Contributor

@kmyk kmyk commented Dec 29, 2019

Range Transform だと曖昧すぎる気がするので Range Affine Range Sum とか Range Linear Range Sum はどうでしょうか? (Affine や Linear は英語として微妙そうだけど)

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 29, 2019

英語がわからないと言う話はあるんですが、動詞を今まで入れてきたので動詞がいいな と書いたところで一応調べたらCompositeが動詞じゃないと言う事実を知りました

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 29, 2019

合成関数の合成を動詞的なアレでやるならcomposeが適切だったのかな? じゃあもうなんでもいいんでaffineにしましょう

@yosupo06 yosupo06 changed the title [問題案] Range Transform Range Sum(range_transform_range_sum) [問題案] Range Affine Range Sum(range_affine_range_sum) Dec 30, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 30, 2019

これ区間のサイズが遅延伝搬に必要ですね 今(想定と愚直が全然会わないので)気づきました

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Dec 30, 2019

まあ区間のサイズが必要なタイプの遅延伝搬はあるあるなので、OKとしましょう

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.

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