概要

\(N\) 冊の本のタイトルが並んだリストに対して、「範囲 \([L, R]\) 内に特定のタイトル \(T\) が何回出現するか」というクエリ \(Q\) 個に効率よく答える問題です。

考察

素朴なアプローチ

各クエリに対して、毎回 \(L\) 番目から \(R\) 番目までをループで走査して \(T\) と一致するかを確認する方法が考えられます。 しかし、この方法では 1 つのクエリに最大で \(O(N)\) の時間がかかります。クエリの数は \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となります。 制約は \(N, Q \le 10^5\) であるため、\(10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

効率的なアプローチ

特定の単語 \(T\) が「どこに出現するか」というインデックス（出現位置）の情報をあらかじめ整理しておくことで、素早く数えることができます。

例えば、タイトルが [apple, orange, apple, grape, apple] と並んでいる場合、apple が出現する位置をリストにまとめると [1, 3, 5] となります。 ここで、「2番目から 4番目の間に apple は何個あるか？」というクエリが来たら、リスト [1, 3, 5] の中で \(2 \le \text{index} \le 4\) を満たす要素の数を数えればよいことになります。

この「ソート済みのリストの中から特定の範囲内の要素の個数を数える」操作は、二分探索を用いることで高速に行えます。

アルゴリズム

1. 前処理:
   • 辞書（ハッシュマップ）を用意し、各タイトルをキー、そのタイトルが出現するインデックスのリストを値として格納します。
   • 本を走査しながらインデックスを追加していくため、各タイトルのインデックスリストは自然と昇順（ソートされた状態）になります。
2. クエリ処理:
   • 検索したいタイトル \(T\) に対応するインデックスリストを取得します。
   • 二分探索（Python では bisect モジュール）を利用して、以下の 2 つを求めます。
     • idx_R: リスト内の要素のうち、\(R\) 以下のものの個数 (bisect_right)
     • idx_L: リスト内の要素のうち、\(L\) 未満のものの個数 (bisect_left)
   • idx_R - idx_L が、範囲 \([L, R]\) に含まれるインデックスの個数となります。

計算量

• 時間計算量: \(O((N + Q \log N) \times |S|)\)
  • 前処理に \(O(N \times |S|)\) かかります（\(|S|\) は文字列の最大長 10）。
  • 各クエリに対して二分探索を行うため、\(O(\log N \times |S|)\) かかります。
  • \(N, Q = 10^5\) であっても、十分に制限時間内に収まります。
• 空間計算量: \(O(N \times |S|)\)
  • すべての単語のインデックスを保存するために、本の総数分のメモリを消費します。

実装のポイント

• 高速な入出力: \(N\) と \(Q\) が大きいため、input() を繰り返すよりも sys.stdin.read().split() などで一括して読み込む方が高速です。

• 二分探索の活用: bisect_left は「指定した値以上の最初の位置」を、bisect_right は「指定した値より大きい最初の位置」を返します。これらを組み合わせることで、特定の範囲内の要素数を \(O(\log N)\) で算出できます。

• 存在しない単語: クエリの単語 \(T\) が一度も出現していない場合、辞書にキーが存在しない可能性があるため、適切にハンドリング（0を返す）する必要があります。

  ソースコード

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

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します。
    # 大量の入力を高速に処理するために sys.stdin.read().split() を使用します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 本の冊数, Q: 問い合わせの数
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 各タイトルの出現位置（1-indexed）をリストに格納する辞書を作成します。
    # キー: タイトル (文字列), 値: そのタイトルが出現するインデックスの昇順リスト
    pos = defaultdict(list)
    for i in range(N):
        title = input_data[2 + i]
        # 問題文に従い、本を1番目から数えたインデックスを保存します。
        pos[title].append(i + 1)
        
    # クエリ情報の開始位置
    query_start = 2 + N
    results = []
    
    # 各問い合わせに対して答えを計算します。
    for j in range(Q):
        # 問い合わせ情報の取得: 左端 L, 右端 R, 検索タイトル T
        base = query_start + 3 * j
        L = int(input_data[base])
        R = int(input_data[base + 1])
        T = input_data[base + 2]
        
        # タイトル T が辞書に存在する場合、二分探索で範囲内の個数を求めます。
        if T in pos:
            indices = pos[T]
            # bisect_right(indices, R) は R 以下の要素の個数を返します。
            # bisect_left(indices, L) は L 未満の要素の個数を返します。
            # その差を取ることで、L 以上 R 以下のインデックスの個数が $O(\log N)$ で求まります。
            count = bisect_right(indices, R) - bisect_left(indices, L)
            results.append(str(count))
        else:
            # タイトル T が一度も出現しない場合
            results.append("0")
    
    # すべての問い合わせ結果を改行区切りで一括出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。