Day 127-Q3 | 区間最頻値クエリ

問題

長さ $N$ の数列 $A_1,\dots,A_N$（$1 \le A_i \le N$）が与えられる。$Q$ 個のクエリに答えよ。各クエリは $L,R$ で与えられ、$A_L,\dots,A_R$ の中で最も多く出現する値の出現回数を出力せよ。

入力形式

N Q
A_1 A_2 ... A_N
L_1 R_1
...
L_Q R_Q

制約

$1 \le N, Q \le 20000$

$1 \le A_i \le N$

$1 \le L_i \le R_i \le N$

入出力例

入力例1

8 3
1 2 2 3 2 1 3 3
1 8
2 5
6 8

出力例1

3
3
2

全体は2・3が各3回。[2,5]=(2,2,3,2)は2が3回。[6,8]=(1,3,3)は3が2回。

概念図

ヒント（段階的開示）

ヒント1（方向性）

区間最頻値はマージ可能な構造を作りにくい（左右の最頻値を合わせても全体の最頻値にならない）。既知の多項式対数時間の一般解法は存在しないため、平方分割でブロック単位に妥協する。

ヒント2（アプローチ）

ブロック区間（フルブロックのみ）の最頻出現回数を全ペア前計算する（$O(N\sqrt N)$）。値ごとの出現位置リストを持ち、二分探索で任意区間内の出現回数を求める。クエリの答えは「中央フルブロックの最頻値」か「境界の半端部分に出現する値」のどちらか。

ヒント3（誘導）

def query(l, r):  # 半開区間[l,r)
    bl, br = l // S, (r - 1) // S
    if bl == br:
        ...  # ブロック内は素直に数える
    best = 0
    if bl + 1 <= br - 1:
        best = block_mode[bl+1][br-1]
    for v in set(A[l:min(r,(bl+1)*S)]) | set(A[max(l,br*S):r]):
        best = max(best, count_in_range(v, l, r))
    return best

模範解答 (Python)

import sys
from bisect import bisect_left
from collections import defaultdict


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    a = [int(data[idx + i]) for i in range(n)]
    idx += n

    S = max(1, int(n ** 0.5))
    num_blocks = (n + S - 1) // S

    pos = defaultdict(list)
    for i, v in enumerate(a):
        pos[v].append(i)

    def count_in_range(v, l, r):
        p = pos.get(v)
        if not p:
            return 0
        return bisect_left(p, r) - bisect_left(p, l)

    block_mode = [[0] * num_blocks for _ in range(num_blocks)]
    for bi in range(num_blocks):
        freq = defaultdict(int)
        best = 0
        for bj in range(bi, num_blocks):
            lo = bj * S
            hi = min(n, lo + S)
            for k in range(lo, hi):
                freq[a[k]] += 1
                if freq[a[k]] > best:
                    best = freq[a[k]]
            block_mode[bi][bj] = best

    out = []
    for _ in range(q):
        L = int(data[idx]); idx += 1
        R = int(data[idx]); idx += 1
        l, r = L - 1, R

        bl, br = l // S, (r - 1) // S
        if bl == br:
            freq = defaultdict(int)
            best = 0
            for k in range(l, r):
                freq[a[k]] += 1
                if freq[a[k]] > best:
                    best = freq[a[k]]
            out.append(str(best))
            continue

        best = 0
        if bl + 1 <= br - 1:
            best = block_mode[bl + 1][br - 1]

        candidates = set()
        for k in range(l, (bl + 1) * S):
            candidates.add(a[k])
        for k in range(br * S, r):
            candidates.add(a[k])
        for v in candidates:
            cnt = count_in_range(v, l, r)
            if cnt > best:
                best = cnt

        out.append(str(best))

    print('\n'.join(out))


solve()

Step-by-Step 解説

1フルブロック前計算
$i$固定・$j$を右に伸ばしながら頻度カウント更新で全ペア $O(N\sqrt N)$。

2境界だけ候補にする理由
境界に出現しない値は中央フルブロックでの回数を超えられない。境界に出現する値だけ数え直せば十分。

3count_in_rangeの二分探索
値の出現位置ソート済みリストへの二分探索で区間内出現回数を $O(\log N)$ で求める。

4クエリの計算量
境界候補は高々$2S$個。1クエリ $O(\sqrt N \log N)$、全体 $O(Q\sqrt N \log N)$。

5実装上の注意
値を復元したい場合はcount_in_rangeループ内で最大値とその値を同時記録すればよい。

よくあるミス

ミス	原因	正しい書き方
区間最頻値をセグメント木でマージしようとする	左右maxが全体最頻値にならない	平方分割+境界候補チェックを使う
block_modeを毎クエリ再計算	前計算を怠る	クエリ前に$O(N\sqrt N)$で一括前計算
境界候補の重複列挙で計算量悪化	set未使用	setで重複除去してからカウント
同一ブロック内クエリでblock_mode[bl+1][br-1]を参照	bl==brで範囲外	同一ブロック内は専用の素朴集計に分岐

次のステップ

発展: 最頻値の値そのもの（最小の最頻値）も同時に求める拡張
次回予告: 頂点追加オンライン木の直径維持（2端点更新の証明とBFS/LCAによる実装）

自己評価

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

Day 127-Q3 — 区間最頻値クエリ（Range Mode Query）

問題