Jasur は n ページの本を読みます。1 日目は a ページ読み、その後は毎日、前の日より k ページ多く読みます(2 日目は a+k ページ、3 日目は a+2k ページ、…)。残りのページが予定より少ない日は、残りを読んで読み終えます。何日目に読み終えるかを求める問題です(1≤n,a≤1012、0≤k≤1012)。
while (hi - lo > eps) のように幅で打ち切ると、浮動小数点数で表せる値が飛び飛びなせいで止まらなくなる例を示し、ループの回数を決め打ちするよう勧めています。必要な回数の見積もり方(初めの幅を 1018、許される誤差を 10−9 とすると 90 回で足りる)と、三分探索の場合の回数も載っています。コードは C++ です。
入れ替えに対応するために、A, B, C の 3 本それぞれについて、和と接頭辞の和の最大値をノードに持たせます。区間内の Ak と Bk をすべて入れ替えると、ノードが持つ A の値と B の値もそのまま入れ替わります。そのため、入れ替えは「3 本の情報を並べ替える」作用として遅延評価セグメント木に載せられます。作用は (0,1,2) の置換 f で表し、新しい i 本目には元の fi 本目の値が入るとします。作用 g の後に f を行うと、新しい i 本目には元の gfi 本目の値が入るので、合成は (gf0,gf1,gf2) です。