ハッシュ関数を設計する

二分木の種類数を数えるために、二分木をハッシュすることを考えてみましょう。どのようなハッシュ関数が考えられるでしょうか？

以下の図のように、\(N\) 頂点の木を長さ \(3N\) の文字列に展開する関数を \(S\) とします。

形式的には、二分木 \(T\) の根の左部分木を \(T_L\)、\(T\) の根の右部分木を \(T_R\) としたとき、\(S(T)\) は以下で定義される文字列です。

\[ S(T) = \begin{cases} \text{\text{empty string}}& (T\text{ is empty})\\ \text{``\verb/{/''} + S(T_L) + \text{``\verb/|/''} + S(T_R) + \text{``\verb/}/''} & (\text{otherwise})\\ \end{cases} \]

この関数は単射であるので、\(S(T)\) をローリングハッシュしたものは、\(T\) のハッシュとして適切です。
また、すべての } を取り除いて、\(S(T)\) の長さを \(2N\) に減らしても単射であるため問題ありません。

問題を変形する

\(C(l, r)\) のハッシュを求める代わりに、\(A_l, A_{l+1}, \dots, A_r\) の最小値を \(A_m\) として、\(C(l, m - 1)\) のハッシュと \(C(m + 1, r)\) のハッシュをそれぞれ求めることにしても良いです。
説明のため、\(C(l, m - 1)\) のみを求めることにします。\(C(m + 1, r)\) も同様に求めることができます。

このように問題を変形することで、区間の右端の位置が制限されるので、問題が解きやすくなります。 具体的には、\(C(l, m - 1)\) は \(C(l, N)\) のある部分木として現れます。したがって、以下のような操作ができればこの問題を解くことができます。

• \(l' = N , N - 1, \dots, 1\) の順に、
  • \(C(l' + 1, N)\) を元に \(C(l', N)\) を作る
  • \(C(l', N)\) のある部分木を文字列にしたときのローリングハッシュを求める

「ある部分木を文字列にしたときのローリングハッシュを求める」ことは、セグメント木で区間のローリングハッシュを管理することで実現できます。
あとは、

• \(l'\) を減らしたときの Cartesian Tree の変化をセグメント木に反映すること
• 部分木に対応するセグメント木の区間がどこか求めること

ができれば良いです。

セグメント木を管理する

\(C(1, N)\) とそれを展開した文字列について、以下のように、どの頂点とどの \(3\) 文字が対応しているかを考えます。

\(C(1, N)\) の頂点の部分集合 \(V\) を \(x, y \in V \implies \operatorname{LCA}(x, y) \in V\) となるように選び、\(A\) から \(V\) の各頂点に対応する要素を取り出した数列を \(A'\)、\(S(C(1, N))\) から \(V\) の各頂点に対応する文字を取り出した文字列を \(S'\) とおきます。 すると、\(S'\) は \(A'\) の Cartesian Tree を展開した文字列と一致することが分かります。 \(V\) が元の数列 \(A\) で区間に対応するならば、「\(x, y \in V \implies \operatorname{LCA}(x, y) \in V\)」の条件は満たされるので、

• 「\(l'\) を減らしたときの Cartesian Tree の変化」は「\(3\) 箇所への文字の追加」である
• 「部分木に対応するセグメント木の区間」は「部分木の根に対応する \(3\) 文字のうち { から } までの区間」である

ことが分かります。

まとめ

まとめると、以下のようにしてこの問題を解くことができます。

1. \(S(C(1, N))\) を求め、各頂点がどの \(3\) 文字に対応するかの表を作る。
2. 長さ \(3N\) のセグメント木でローリングハッシュを管理する。はじめ、各要素は空文字列のハッシュである。
3. \(l' = N, N - 1, \dots, 1\) の順に:
   1. 頂点 \(l'\) に対応する \(3\) 文字をセグメント木に追加する。
   2. \(l = l'\) であるような各クエリについて、\(S(C(l, m - 1))\) のハッシュを求める。
4. 長さ \(3N\) のセグメント木を用意する。
5. \(r' = 1, 2, \dots, N\) の順に:
   1. 頂点 \(r'\) に対応する \(3\) 文字をセグメント木に追加する。
   2. \(r = r'\) であるような各クエリについて、\(S(C(m + 1, r))\) のハッシュを求める。
6. ハッシュの組が何種類あるか数える。

計算量は \(O((N + Q) \log (N + Q))\) 時間です。

実装例 (C++)