【ACL】遅延セグメント木

セグメント木は前に備忘録書いてなんとなくわかった気になっていたが、
遅延セグ木は使い方よくわからんかった。

宣言しておくもの

  • S：データの型。intとかなら不要。普通のセグ木と同じ。
  • S op(S a, S b)：ノード間からどういう値を抽出するか。普通のセグ木と同じ。
  • S e()：opに対しての単位元。普通のセグ木と同じ。
  • F：値の更新（写像）の型。intを足すとかだったらint
  • F mapping(F f, S x)：区間の値更新の関数。あるデータx（seg[i]とか）にfを作用させたときの関数？int足すならreturn x+f;
  • F composition(F f, F g)：2つの写像f,gを、f・g・seg[i]と作用させたとき、f・gがどういう写像になるか。
  • F id()：（疑似的な）恒等写像。


要素の更新が「ある値に変更する」だった場合。
mapping, composition, idをうまく定義してやる必要がある。
atcoder.jp



このサイトのおかげで理解できました。
AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

数列　区間　種類数

c++ 競技プログラミング AtCoder

典型力。

ダブったペアのぶん種類数が減る。
ダブったペアの数え上げにfenwicktreeを使う。

atcoder.jp

fenwicktreeにどう情報を入れるか、数え上げをどう実現するかがミソでしょうか。

備忘録 ラムダ式とかダイクストラとか

いろいろ勉強になったので、自分用備忘録。
内容は
・priority_queueのgreatorとか使った宣言
・それを使ったダイクストラ敵なの
・ラムダ式使ったpriority_queueのemplace
・文字列操作いろいろ


atcoder.jp


ほかにダイクストラ使ったやつ
https://atcoder.jp/contests/abc192/submissions/20367635