ei1333の日記

ぺこい

log をつけずに解くのが好きな人向けの記事2

はい

log をつけずに解くのが好きな人向けの記事 - えびちゃんの日記に影響されました

RMQ

配列を使うことによりクエリあたり ${O(r - l)}$ です

中央値

それぞれの要素についてそれが中央値になるかを試すことにより ${O(n^2)}$ で求められます（自分より小さい要素の個数を数えればよいです）

篩による素数判定

全ての値についてそれが素数かどうか判定すればよく ${O(n \sqrt n)}$ です

過半数

中央値と同じノリでそれぞれの要素についてそれと一致する要素の個数を数えることにより ${O(n^2)}$ です

行最小値

それぞれの行について行の最小値を調べることにより ${O(n^2)}$ です

接尾辞配列

3秒考えましたが思いつきませんでした　どうやったらlogをつけずに解けるのでしょうか

→ https://twitter.com/_primenumber/status/1608997210406125569?s=46&t=ySFJ3Q87tiI0MpHzsCKP5g

最小共通祖先

祖先を総当たりすることによりクエリあたり ${O(n)}$ です

Decremental neighbor query

配列を使うことによりクエリあたり ${O(n)}$ です

Level ancestor

対象の頂点から根の方向に向かって頂点を列挙することによりクエリあたり ${O(n)}$ です

飽きました