library-checker-problems
library-checker-problems copied to clipboard
yosupo06
[問題案] Range Update All Frequency
問題名: Range Update All Frequency
問題概要
長さ $N$ の数列 $A _ 0, A _ 1, \ldots, A _ {N-1}$ が与えられる．$Q$ クエリ処理
1 L R X: $i = L, L+1, \ldots, {R-1}$ について，$A _ i \leftarrow X$
2 X: $i = 0, 1, \ldots, N-1$ のうち，$A _ i = X$ であるものの個数を答える
制約
- $1 \leq N, Q \leq 500000$
- $1 \leq A _ i, X \leq 10^9$
解法
同じ値のところを set などで管理するテク
定数区間を適切に管理する。というのが問いたいものであるならば、 aa,bbb と a,a,b,b,b とかで答が変わるようにする（つまり区間の個数が最小になるようにして定数区間を管理させる）のが良いと思ったのですが、どうですか？（例えば $A_l = \cdots = A_{r-1} = X$ となる $(l,r)$ の数え上げとか）
ランレングス圧縮で $a$ が $c$ 個あるとしたときの $\sum x _ a y _ c$ や $\sum x _ a ^ c$ を出力とかどうでしょうか。
$a$ が $\lbrack l , r \rparen$ に存在するときに $\sum x _ a y _ l z _ r$ を出力させても良いかもしれません。
いかにも普段ぜんぜん見ないような問い方をしてびっくりさせてしまうのがちょっと。 何のライブラリに関する問題かとかが経緯を知らないと理解しにくくなるかも。 そこまできちんとやらなくてもいいのでは？という気がしています。
単に区間を管理するライブラリを対象とした問題ということで、次のようにしたいと思います。（セグメント木も使うタイプは https://judge.yosupo.jp/problem/range_set_range_composite ということで）
- 1 L R X: $A _ i \leftarrow X$
- 2 i： $x=A_i$ を含む極大な定数区間を答える（l r x を出力）
注意：(cf. Range Set Range Composite https://github.com/yosupo06/library-checker-problems/pull/1085) 更新区間の選び方が一様ランダムだと、十分な回数の更新後のデータ構造のサイズが期待的にかなり小さくなります。
