CodeChef - Chef and Array

• 問題

区間の半数を超える同一要素(dominator)があるかどうか判定するクエリ問題。一点更新もある。

方針 1

Editorialの方針。

2つの区間を合併するとき、ある要素が合併後の区間で半数を超えるためには、2つの区間のうちの少なくともいっぽうで半数を超えていなくてはならない、ということを利用できる。

セグメント木の各ノードに、区間内の各要素の出現頻度を保持するマップと（存在すれば）区間のdominatorを保持しておく。質問クエリに対しては、質問の区間がセグ木上の${O}(\log N)$個の区間に分割できるので、${O}(\log N)$個のdominatorの候補を、${O}(\log N)$個のマップに関して調べる。${O}(N \log N + Q \log^2 N)$だが、ハッシュテーブルを使う${O}(\log^2 N)$なのでかなり重い。

https://www.codechef.com/viewsolution/42694801 1.63 sec.

方針2

$n, k$を決めておいて、質問クエリの度に区間から$n$回無作為に要素を抽出して$k$回以上出現した要素についてrange frequency queryを適用してdominatorかどうか調べる。

正答率を評価するには二項分布のCDFを調べればよい。たとえば100回抽出して17回以上出現した要素について調べることにすると、確率1/2で成功する試行を100回繰り返して成功回数が16回以下になる確率が$10^{-11}$以下で、$10^5$個の質問に対して少なくとも1回間違える確率は$10^{-6}$以下と求まる。

https://www.codechef.com/viewsolution/43903194 0.68 sec.

方針 3

rajat1603さんの書き込みより。

区間内でトーナメントのようなことをする。セグメント木の各ノードに$(x, 残っているxの数)$を保持することにして、葉$(a_i, 1)$から

$$(x_1, c_1) \oplus (x_2, c_2) = \begin{cases} (x_1, c_1 + c_2) \qquad \text {if} \ x_1 = x_2 \\ (x_1, c_1 - c_2) \qquad \text {else if}\ c_1 \ge c_2 \\ (x_2, c_2 - c_1) \qquad \text{otherwise} \\ \end{cases}$$

という演算でマージしていくと（結合法則は成り立たないが）マージの順番や区間の大きさによらず、dominatorは必ず残る。実際に残った要素がその区間でdominatorかどうか判定するためにはrange frequency queryに答えらればよい。${O}((N+Q) \log N)$。

https://www.codechef.com/viewsolution/42748384 0.22 sec.

方針4

anudeep2011さんの書き込みより。

区間の長さの閾値$B$を適当に決めて、長さ$B$未満の区間は愚直に判定する。

長さ$B$以上の区間については、その区間のdominatorは与えられた列中に$B/2$個より多く含まれることを利用できる。具体的には、列中に$B/2$個より多く存在する数については個別にBIT等を作っておいて、range frequency queryに答えられるようにする。このような数は高々$2N/B$種類しかないので、質問に対しては$2N/B$個のBITをすべて調べれば答えられることになる。

前処理: ${O}(N \log N \cdot (N/B))$ 質問クエリ（長さ$B$未満）: ${O}(B)$ 質問クエリ（長さ$B$以上）: ${O}((N/B) \log N)$ 更新クエリ: ${O}(\log N)$

$B = \sqrt { N \log N}$とすると${O}((N+Q) \sqrt {N \log N})$。