Day 156-Q4 | Boyer–Moore 多数決 + 区間多数派クエリ

問題

長さ $N$ の数列 $A$ と $Q$ 個のクエリ $(l_j,r_j)$。各クエリについて、区間 $A_l,\dots,A_r$ の中に区間長の半分より多く（厳密に $>\frac{r-l+1}2$ 回）出現する値があればそれを、なければ $-1$ を出力せよ。

入力形式

N Q
A_1 ... A_N
l_1 r_1
...
l_Q r_Q

制約

変数	範囲	補足
$N,Q$	$1\le N,Q\le2\times10^5$	$O(NQ)$ 走査は $4\times10^{10}$ で不可
$A_i$	$1\le A_i\le10^9$	座標圧縮不要（辞書で位置管理）
$l_j,r_j$	$1\le l_j\le r_j\le N$	1-indexed 閉区間

入出力例

入力例1

9 5
3 1 3 3 2 3 1 3 3
2 8
1 4
4 5
1 9
5 7

出力例1

$[5,7]$ は $2,3,1$ で多数派なし。$[4,5]$ は $3,2$ が 1 回ずつで多数派なし。

概念図：Boyer–Moore のカウンタ軌跡（$A=[3,1,3,3,2,3,1,3,3]$・実測）

ヒント（段階的開示）

ヒント1（方向性）

まず配列全体の過半数値をカウンタ 1 個と候補 1 個で見つける Boyer–Moore の多数決を復習する。候補が一致すれば +1、違えば −1、0 になったら候補を入れ替える。「異なる 2 つを相殺しても過半数の値は必ず生き残る」が核心。ただし多数派が無いときも何かを返すので、候補は必ず検証する。

ヒント2（アプローチ）

状態 $(\text{cand},\text{cnt})$ は 2 つの区間の要約を合成できる：同じ候補なら $(c,n_1+n_2)$、違えば大きい方から小さい方を引く。結合的なのでセグメント木の各ノードに持てば任意区間の候補が $O(\log N)$。候補の実出現回数は値ごとの位置リストへの bisect で $O(\log N)$。

ヒント3（誘導）

def merge(x, y):
    c1, n1 = x; c2, n2 = y
    if n1 == 0: return y
    if n2 == 0: return x
    if c1 == c2: return (c1, n1 + n2)
    return (c1, n1 - n2) if n1 >= n2 else (c2, n2 - n1)

# 葉は (A[i], 1)。クエリ: cand = tree.query(l, r)[0]
# cnt = bisect_right(pos[cand], r) - bisect_left(pos[cand], l)
# 答え = cand if 2*cnt > r-l+1 else -1

模範解答 (Python)

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict

def merge(x, y):
    """Boyer-Moore の要約 (cand, cnt) 同士の合成。結合的なのでセグメント木に載る"""
    c1, n1 = x
    c2, n2 = y
    if n1 == 0:
        return y
    if n2 == 0:
        return x
    if c1 == c2:
        return (c1, n1 + n2)
    return (c1, n1 - n2) if n1 >= n2 else (c2, n2 - n1)

class SegTree:
    def __init__(self, a):
        n = 1
        while n < len(a):
            n *= 2
        self.n = n
        self.t = [(0, 0)] * (2 * n)
        for i, x in enumerate(a):
            self.t[n + i] = (x, 1)
        for i in range(n - 1, 0, -1):
            self.t[i] = merge(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l, r):  # [l, r)
        L = (0, 0); R = (0, 0)
        l += self.n; r += self.n
        while l < r:
            if l & 1:
                L = merge(L, self.t[l]); l += 1
            if r & 1:
                r -= 1; R = merge(self.t[r], R)
            l >>= 1; r >>= 1
        return merge(L, R)

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    pos = defaultdict(list)                 # 値 -> 出現位置（昇順）
    for i, x in enumerate(a):
        pos[x].append(i)
    st = SegTree(a)
    out = []
    idx = 2 + n
    for _ in range(q):
        l = int(data[idx]) - 1; r = int(data[idx + 1]) - 1
        idx += 2
        cand, _ = st.query(l, r + 1)
        p = pos[cand]
        cnt = bisect_right(p, r) - bisect_left(p, l)   # 候補の実出現回数で必ず検証する
        out.append(cand if 2 * cnt > r - l + 1 else -1)
    print("\n".join(map(str, out)))

main()

Step-by-Step 解説

1なぜ過半数は生き残るか
候補以外の値が来るたびに候補 1 個と相殺するので、相殺されるペアは高々 $\lfloor N/2\rfloor$ 組。過半数の値は相殺しきれずに残る。$A=[3,1,3,3,2,3,1,3,3]$ では候補 3・最終カウント 3・実出現 6 回で確定（実測）。

2検証が必須な理由
$B=[1,2,3,1,2,4]$ に対して候補 2 が返るが、出現 2 回で $6/2=3$ を超えない（実測）。アルゴリズムは「多数派があるならそれ」しか保証しない。

3区間クエリの実測

クエリ（1-idx）	セグ木の $(\text{cand},\text{cnt})$	実出現 / 長さ	答え
$[2,8]$	(3,1)	4 / 7	3
$[4,5]$	(3,0)	1 / 2	−1
$[5,7]$	(1,1)	1 / 3	−1

乱択 2000 セット × 20 クエリで全探索と不一致 0 件。

迷った他案と採らなかった理由（$N=Q=2\times10^5$ 実測）

案	計算量	実測	採否
各クエリで区間走査	$O(NQ)$	未実行（$4\times10^{10}$）	却下
セグ木 + bisect 検証	$O((N+Q)\log N)$	0.99 s	採用（決定的）
乱択 20 サンプル + 検証	$O(20Q\log N)$	2.72 s・セグ木と不一致 0	不採用。見逃し確率 $\le2^{-20}$ で実用上十分だが、Python の乱数コストで決定的の方が速かった。C++ なら逆転しうる（未実測）
Misra–Gries（候補 $k-1$ 個）	$O(k)$ 要約	—	「$>N/k$」の一般化には必要だが $k=2$ では過剰。$k=3$ で得た要約 {3:5, 1:1} は 3 の真の回数 6 を過小評価（実測）で検証必須

よくあるミス

ミス	原因	正しい書き方
候補をそのまま答えにする	多数派が無くても候補は返る	必ず実出現回数で検証
cnt == 0 の要約を通常ノード扱い	単位元 (0,0) と候補 0 の区別が曖昧	n1 == 0 / n2 == 0 を最初に処理
合成の左右を入れ替える	単位元処理の順序で cand が変わりうる	merge(L, node) / merge(node, R) の順序を保つ
1-indexed をそのまま渡す	添字ずれ	半開区間 [l-1, r) に変換

次のステップ

関連する実問題: LeetCode 169「Majority Element」（原型）、229「Majority Element II」（Misra–Gries $k=3$）。AtCoder の区間最頻値は Day 127（平方分割）
発展: 点更新を許す（pos を値ごとの平衡木／BIT に置き換え）
扱わなかった範囲: 「$>\frac{r-l+1}k$」の一般化と候補検証コスト $O(k\log N)$ の実測
次回予告: 非凸多角形の点包含判定（Winding Number）

自己評価

完全理解おおむね理解要復習

Day 156-Q4 — Boyer–Moore 多数決 + 区間多数派クエリ（Range Majority・セグメント木上のマージ）

問題