[問題案] Point Set Range Composite (Large)

[SSRS-cp]

問題名: Point Set Range Composite (Large)

問題概要

#122 と同じ。ただし、N≦10^9

想定解法: 必要なところだけ作るセグ木

メモ・検討事項

• Point Add Range Sum, Point Set Range Composite, Range Affine Range Sum のうちどれを作るか？(複数という可能性もある)
• 問題名をどうするか

[maspypy]

point set と range affine で セグ木 / 遅延セグ木 の 2 種あるとよいのでは。
（メモリ定数倍が大きいことが多いので、作用素の有無でライブラリを分けたい）

ただし

・N が小さい版でもこれを verify できる（が、同解法の中での速度比較はしにくい）
・最速実装はクエリ先読み座圧になってしまいそう（ので、同解法の中での速度比較はしにくい）

とかはありますね。

[SSRS-cp]

N が小さい版でもこれを verify できる

N が大きい版を作るメリットとして、「無駄なノードを省略することで Θ(QlogN) から Θ(QlogQ) に落とすテク」の verify ができます

[maspypy]

• Point Set Range Composite
  はじめ $f_i(x) = 1x+0$ である
  空間 $O(Q\log N)$ 計算量 $O(Q\log N)$ → 空間 $O(Q)$ 計算量 $O(Q\log N)$ にできる

• Range Affine Range Sum
  はじめ $a_i = 0$ である
  空間 $O(Q\log N)$ 計算量 $O(Q\log N)$

[maspypy]

↑ こうだと思いました

@SSRS-cp

「無駄なノードを省略することで Θ(QlogN) から Θ(QlogQ) に落とすテク」

これって合ってますか？ $Q\log Q$ というのはどこにも出てこないと思ったのですが。

[SSRS-cp]

書いたときのことをあまり覚えていないのですがおそらく $O(Q)$ の勘違いでした、すみません

[maspypy]

ありがとうございます。

[maspypy]

#828 (comment)

この 2 問で良さそうです。

[maspypy]

Range Affine の方がまだ