操作と Stern–Brocot tree の関係

Stern–Brocot tree (SBT) は無限に続く完全二分木であり、各ノードには既約分数が割り当てられています。ここに、 \((0,1)\) と \((1,0)\) 両方を含む頂点を追加し、新しい根とすることで \((1,1)\) の深さを \(1\) にした木 SBT+ を考えます。

問題文中の

はじめ \(A=((0,1),(1,0))\) です。

あなたは \(A\) に対して次の操作を \(0\) 回以上何度でも行うことができます。

• 隣り合う \(2\) つの整数組 \((a,b),(c,d)\) を自由に選び、その間に \((a+c,b+d)\) を挿入する。

という操作は、

• はじめ、 SBT+ の根にマークが付いている。
• 各操作では、マークが付いているノードを \(1\) つ選び、その子のうち片方にマークを付けることができる。

と言い換えることができます。すると、 \(f(T)\) は \(T\) の要素にマークを付けるのに必要な操作回数です。結局、 \(T\) の要素いずれかの祖先であるような要素の個数ということになります。

現れない要素の処理

\(\gcd(a,b)\neq1\) の要素は作れないので、ここで問題が分割されます。分割した後の列をそれぞれ解いて答えを足します。

Stern–Brocot tree に関する計算・ virtual tree の構築

根から既約分数 \(a/b\) までのパスについて、左の子に移動することを L 、右の子に移動することを R と表し、連長圧縮すると、これはユークリッドの互除法から構築されるため高々 \(|a|,|b|\) の上限の対数オーダーのサイズになります。より具体的なアルゴリズムは Nyaan さんによる解説 を参考にしてください。

連長圧縮されたパスを用いると、 LCA の深さは、単に列を先頭から比較するアルゴリズムで計算できます。

SBT における通り掛け順は、既約分数の値の順に一致するので簡単に整列できます。整列された状態で、各要素の深さと隣接要素の LCA の深さを交互になるように並べ、その cartesian tree を得ると、これを virtual tree として利用することができます。

木のパスクエリへの帰着

「 \(f(S _ {l,r})\) によるノード \(x\) の寄与」を、「 \(r\) まで走査した時点でノード \(x\) に割り当てた整数 \(q _ x\) が \(l\) 以上である」と言い換えると、全体の答えを出す過程を次のクエリ問題で表せます。

• \(r\) を \(1\) から始めて \(1\) つずつ増やす。
• \(r\) の値を訪れるたび、 \(r\) 番目の要素 \((a,b)\) に対応するノードと根の間のパス上の頂点 \(x\) について、 \(q _ x\) の値を \(r\) で上書きする。
• その後、 \(q _ x\) の値の総和を求める。

高速な処理方法

得られた木を HL 分解すると、次の設定でクエリを合計 \(O(N\log N)\) 回処理することになります。

• はじめ、数列 \(a_1,a_2, \ldots ,a_{10^{100}}\) の要素をすべて \(0\) にする。（この数列は十分長いと考える）
• クエリでは \(p\) , \(v\) が与えられるので、 \(a_1,a_2, \ldots ,a_p\) の値を \(v\) で上書きする。これによる \(a_1,a_2,\ldots ,a_{10^{100}}\) の総和の変化分を取得する。

これをスタックで管理すれば全体 \(O(N\log N)\) 時間です。

以上より、全体の計算量を \(O(N (\log X + \log N))\) （ここでの \(X\) は、 \(a\) , \(b\) として与えられる値の上限）とすることができます。

実装例

投稿者の実装 : C++ , 152ms