yukicoder contest 222（セグメント木コンテスト）

遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト（2019/9/6開催）の問題を解いてみた。
難しいけど面白かった（解けたので）。

A - 875. Range Mindex Query（★★☆）

type1: 順列の2点を交換する更新操作
type2: 区間のargminを求めるクエリ（※順列なので一意）

1点更新-区間minクエリの（普通の）セグ木を用意
順列をセグ木に投入
どの値がどこにあるかをmap<int,int>に入れておく
値の交換のために、ある点から上に辿って（INT_MAXとかで）リセットする機能を追加
交換は2点リセット+2点更新で
クエリして得られた最小値がどこにあるかをmapから得ればargmin相当

→AC

B - 876. Range Compress Query（★★★）

type1: 区間に $+x$ する更新操作
type2: 区間について関数 $F(l,r)$ の値を求めるクエリ

$F(l,r)$ は区間[l,r]で何回数が変わったかを調べる関数。（変わった回数+1が値）

(1)遅延セグ木+BIT

区間add-区間sumクエリの遅延セグ木を用意（クエリは1点を得るだけなのでsumでもmaxでもminでもいい）
それとは別に1点更新-区間sumクエリがしたいのでBITでも用意
- このBITには、隣接する2値が同じならば0、異なれば1を入れる
区間の操作では、BITの状態が変わりうるのは区間の両端のみ
- 両端の隣接2値の比較結果を更新
$F(l,r)$ の値はBITのsumクエリで得られた値+1

→AC

(2)BIT×2本

区間add-区間sumクエリを行う部分をBITでやる
- 微分した操作（imos法みたいに、区間の始点に+x、終点の次に-xを置く）
- 初期値も $+a_i$ の次に $-a_i$ を置く感じで入れる
- こうすると、ある点の値は BIT.sum(0,場所) で求まる
これを利用して隣接2値の比較結果を（もう1本のBITで）更新して
あとは同じ

→AC

C - 877. Range ReLU Query（★★★）

ReLUって＿／みたいなあれだよね？

type1: 区間の $\sum ReLU(a_i)=\sum \max(a_i-x,0)$ を求めるクエリ

$\sum \max(a_i-x,0)=\sum (\max(a_i,x)-x)=\sum \max(a_i,x)-x(r-l+1)$
とか変形できるけど

調べたいxより大きな $a_i$ だけの合計がその区間で求められれば良い？
その区間にそういう $a_i$ がいくつあるかも欲しいけどどうする？
クエリ先読み。xを降順ソート

$a_i$ を大きい順にBITに投入: BIT1.add(i,a_i)
を投入した場所をもう1本BITを用意して記録: BIT2.add(i,+1)
- xを何回引けばいいかが求まる
次のより大きいxについてのクエリを行い結果を配列の該当場所に記録しておく
- クエリの区間について BIT1.sum(l,r) - x*BIT2.sum(l,r)
最後に結果を一括出力

→AC

D - 878. Range High-Element Query（★★★）

type1: 指定区間の各値が「高い」か、即ち、その区間の自分より左に自分より大きな値を持たないかを見て、「高い」値の個数を返す

ある値がどの範囲で「高い」と言ってもらえるかを調べておく
- 区間の始点はRMQなりセグ木maxクエリで二分探索すれば分かる。終点はその値の位置
クエリ区間で「高い」と言える値とは？
- 「高い」範囲がクエリ始点より前（始点含む）で始まって、クエリ区間内で終わる値
- 「1.始点がクエリ始点かそれより前にある」「2.終点がクエリ区間内にある」
- 1について考えなくて済むなら2.をBITか何かで数えればよい
- そのためには…範囲の始点順に値をソートして投入しつつ、（クエリのほうもソートしておいて）それと同じか遅く始まるクエリを順次投入していけばよさそう

→AC

E - 879. Range Mod 2 Query（★★★★）

type1: 区間を%=2 する更新操作
type2: 区間を+=x する更新操作
type3: 区間のsumを求めるクエリ

これが出来る遅延セグ木をどう組む？
遅延したい演算の合成が難しいな

+=x +=x の連続は合成可能
%=2 ... %=2 と来たら最後以外の%=2は消せる

みたいなのは分かるんだけど

遅延操作を (x, %=2するかしないか) みたいに表現できる？
これで合成するには... (x, %=2する) の後に (x, %=2しない) が来たら合成できない…
合成できない場合先に下に送るとか？書いてみたけどうまく行かない

考え方を変えてみる

遅延操作をリスト（vectorで書いたけど）として持って後ろに繋いでいけば？
実際には前述の縮約が可能（合成時に短くできる）

(false, x) : +=x操作
(true, 0) : %=2操作

みたいに

うまく行った
→AC

F - 880. Yet Another Segment Tree Problem（★★★★☆）

type1: 区間に x を代入する更新操作
type2: 区間に gcd(*,x) する更新操作
type3: 区間のmaxを求めるクエリ
type4: 区間のsumを求めるクエリ

maxクエリ用とsumクエリ用で別々に遅延セグ木を立てる？いや一本で両方持てばいいっしょ
xの代入はまあ楽か（その区間のmaxはxになるしsumは $x\times (r-l+1)$ になる）
問題はgcdの方で

何かとxのgcdは必ずxの約数になる（ということは1〜xの範囲に収まる）はず

とりあえず遅延操作の表現を考える。Eみたいにリスト（vector<pair<bool,long long>>）にしてみる？




(false, x) : gcd更新
(true, x) : =x（代入）更新


代入はそれまでの操作の結果が関係なくなるので操作列の最後の代入以前は捨ててよい
gcd(gcd(a,x),y) = gcd(a,gcd(x,y)) みたいな交換が効くので縮約できる
とすると操作列が長さ2を超えることはなさそう。(空, =x, gcd, =x gcd,の4種類しかありえない）
遅延操作の方はこれで良いとして、各ノードが（maxとsum以外に）持っておくべき値は何？

素因数分解して集計しても計算は簡単にできないな
何が何個あるかだけmapにして持たせる？（それだとmax,sumの更新にも都合がよさそう）

でも（gcd後なら）xの約数の個数を超えないとはいえそれなりに大きいよね…

時間制限が5secなので少しは重くても行ける？
最初に投げたやつは大きな（大きそうな）データでTLE。

（TLEが1つ出るとその後のジャッジをしないの賢いなあ）

しかし巨大データを貰ってきて試したら48secほどかかっていた。


std::mapをstd::unordered_mapにするとか
更新操作 a=f(a,b) をf(&a,b)みたいに書き換えたりとか
巨大mapを含む部分のコピーをできるだけ減らしたい...

なるべく参照渡しにする

10〜12secで終わるようになった。（でも5secにはまだ遠い）
それを投げてみたら→AC

お
時は2020年。ローカル（5年物Macbook）よりジャッジの方が早い時代か...

naoya_t@hatenablog

いわゆるチラシノウラであります