導入 配列 $a = (a_0, a_1, \dots, a_{n-1})$ に対して適当な区間 $[l\lldot r)$ が与えられて、そこでの平均値 $f_a(l, r) = \tfrac1{r-l}\sum_{i=l}^{r-1} a_i$ を考えます。 たとえば $[l\lldot r)$ がたくさん与えられて平均値を求めるだけなら、累積和…

ポインタ系データ構造（未定義お気持ち用語）を書きましょう。 まえがき やりたいね 基礎パート ツールの紹介 練習パート 実践パート データ構造に関して補足 勉強パート あとがき おわり まえがき ここでポインタ系データ構造と呼んでいるのは、配列や二分…

お風呂で思いついたシリーズです。 できる操作は次の通りです。 $\texttt{new}()$ $∅$ で初期化する $S.\texttt{insert}(x)$ $S ← S ∪ \{x\}$ で更新する $S.\texttt{remove}(x)$ $S ← S \smallsetminus \{x\}$ で更新する $S.\texttt{less}(a)$ $\max {\{x∈…

背景としては、こちらの記事です。 rsk0315.hatenablog.com 1431655766, 1717986920, 1431655782, 1431655768, 1840700272, 1431655966, -1431655056 などさまざまなマジックナンバーが登場します。 「$x$ が $3$ の倍数であることがわかっているとき、$1431…

何らかの順序を持った型 T: Ord があって、それに関する何らかの（多重）集合の中央値を求めるライブラリを作りたいとします。 たとえば単に配列 a: [T] の中から中央値を探すだけだったり、a: [T], b: [T] から a[i] + b[j] として考えられるものの中央値 (…