概要

本のタイトルが並んだ列に対して、指定された区間内で特定のタイトルと完全一致する本の数を求める問題です。

考察

素朴なアプローチでは、各クエリごとに区間 \([L_j, R_j]\) 内の全ての本を調べる方法が考えられます。しかし、\(N\) と \(Q\) が最大 \(10^5\) まで大きくなるため、この方法では時間計算量が \(O(NQ)\) となり、最悪ケースで \(10^{10}\) 回の操作が必要になってしまいます。これは制限時間内に処理できません。

そこで、各タイトルに対してそのタイトルを持つ本の位置（インデックス）を事前に記録しておき、二分探索を用いて効率的に区間内の個数を数える方法が有効です。これにより、各クエリを対数時間で処理できるようになります。

アルゴリズム

1. 前処理: 各タイトル \(S_i\) に対して、そのタイトルが出現する位置（インデックス）のリストを辞書で構築します。

   • 例: タイトル “abc” が位置 1, 3, 5 にある場合、pos_map["abc"] = [1, 3, 5] となります。

2. クエリ処理: 各クエリ \((L_j, R_j, T_j)\) に対して:

   • \(T_j\) が辞書に存在しない場合は、即座に 0 を返します。
   • \(T_j\) が存在する場合、対応する位置リストに対して二分探索を行います。
     • bisect_left(indices, L) で、区間の左端 \(L_j\) 以上となる最初の位置を探します。
     • bisect_right(indices, R) - 1 で、区間の右端 \(R_j\) 以下となる最後の位置を探します。
   • 見つかった範囲の要素数を計算して返します。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 前処理: 各タイトルの位置を記録するのに \(O(N)\)
  • クエリ処理: 各クエリごとに二分探索で \(O(\log N)\)、全体で \(O(Q \log N)\)
• 空間計算量: \(O(N)\)
  • 辞書が最大 \(N\) 個の要素を保持するため

実装のポイント

• defaultdict(list) を使って、各タイトルに対する位置リストを効率的に構築します。

• 二分探索には標準ライブラリの bisect モジュールを使用します。

• bisect_right は指定した値より大きい最初の位置を返すため、-1 して最後の有効な位置を取得する必要があります。

• クエリ処理時にタイトルが辞書に存在しない場合の処理を忘れないようにします。

  ソースコード

import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    
    n, q = map(int, data[0].split())
    titles = data[1].split()
    queries = []
    for i in range(2, 2 + q):
        parts = data[i].split()
        L = int(parts[0])
        R = int(parts[1])
        T = parts[2]
        queries.append((L, R, T))
    
    pos_map = defaultdict(list)
    for idx, s in enumerate(titles, start=1):
        pos_map[s].append(idx)
    
    results = []
    for L, R, T in queries:
        if T not in pos_map:
            results.append(0)
            continue
        
        indices = pos_map[T]
        left_index = bisect.bisect_left(indices, L)
        right_index = bisect.bisect_right(indices, R) - 1
        
        if left_index <= right_index:
            count = right_index - left_index + 1
            results.append(count)
        else:
            results.append(0)
    
    for res in results:
        print(res)

import bisect

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。