概要

本のタイトルから指定された区間に含まれる特定のタイトルの出現回数を高速に求める問題です。

考察

この問題では、最大で \(10^5\) 個の本と \(10^5\) 回の問い合わせがあり、素朴に毎回区間を走査すると、全体で \(O(N \times Q) = O(10^{10})\) の計算が必要になり、時間内に処理できません（TLE）。

そこで、事前に各タイトルに属する本の位置（インデックス）を記録しておき、問い合わせがあるたびに「ある範囲内にある特定のインデックスの数」を高速に求めることを考えます。これは、インデックスリストをソートしておけば、二分探索によって効率的に求めることができます。

例えば、タイトル "abc" の本がインデックス \([2, 5, 8, 12]\) にあったとすると、区間 \([3, 10]\) 内にある "abc" の本の数は、これらのインデックスの中で \(3\) 以上 \(10\) 以下のものを数えることで求められます。これは bisect_left と bisect_right を使うことで、\(O(\log N)\) で計算できます。

アルゴリズム

1. 各タイトルに対して、そのタイトルを持つ本のインデックスをリストで保持します。これは事前処理として \(O(N)\) で可能です。
2. 各問い合わせに対して：
   • タイトル \(T_j\) に対応するインデックスリストを取得します。
   • このリストに対して、区間 \([L_j, R_j]\) に含まれるインデックスの個数を二分探索で求めます。
     • bisect_left(indices, L)：\(L\) 以上の最小の位置
     • bisect_right(indices, R)：\(R\) 以下の最大の位置＋1
     • 差分が該当個数になります。
3. 結果を出力します。

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • インデックスリスト構築: \(O(N)\)
  • 各クエリ処理: \(O(\log N)\)、全部で \(Q\) 回
• 空間計算量: \(O(N + Q)\)
  • タイトルごとのインデックス保存に \(O(N)\)、入力と出力に \(O(N + Q)\)

実装のポイント

• インデックスは 0-based に揃える（入力が 1-based なので 1 引く）
• 文字列比較は完全一致のみなので、辞書 (defaultdict) を使って各タイトルの出現位置をリストで管理するのが効率的
• bisect モジュールを使うことで、ソートされたリストに対する範囲クエリを高速に処理できる

## ソースコード

```python
import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    S = data[2:2+N]
    
    # 各タイトルに対して、そのタイトルを持つ本のインデックスリストを保持
    title_indices = defaultdict(list)
    for i in range(N):
        title_indices[S[i]].append(i)
    
    # 各タイトルのインデックスリストをソートしておく（すでにソートされているが念のため）
    for title in title_indices:
        title_indices[title].sort()
    
    result = []
    idx = 2 + N
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexedに変換
        R = int(data[idx+1]) - 1
        T = data[idx+2]
        idx += 3
        
        if T not in title_indices:
            result.append("0")
            continue
        
        indices = title_indices[T]
        # 二分探索でL以上の最小のインデックスとR以下の最大のインデックスを見つける
        from bisect import bisect_left, bisect_right
        left_pos = bisect_left(indices, L)
        right_pos = bisect_right(indices, R)
        count = right_pos - left_pos
        result.append(str(count))
    
    print("\n".join(result))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。