Open SSRS-cp opened 1 year ago
All Composite か、セグ木無しでやりたいなら集合ハッシュを出力させるのが良いかなという気がします。
定数区間を適切に管理する。というのが問いたいものであるならば、 aa,bbb と a,a,b,b,b とかで答が変わるようにする(つまり区間の個数が最小になるようにして定数区間を管理させる)のが良いと思ったのですが、どうですか?(例えば $Al = \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 ということで)
注意:(cf. Range Set Range Composite https://github.com/yosupo06/library-checker-problems/pull/1085) 更新区間の選び方が一様ランダムだと、十分な回数の更新後のデータ構造のサイズが期待的にかなり小さくなります。
問題名: 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$ であるものの個数を答える制約
解法
同じ値のところを
set
などで管理するテク