Overview

Given a list of \(N\) book titles, we need to efficiently answer \(Q\) queries of the form: “How many times does a specific title \(T\) appear within the range \([L, R]\)?”

Analysis

Naive Approach

For each query, we could scan from the \(L\)-th to the \(R\)-th element in a loop and check whether each matches \(T\). However, this method takes up to \(O(N)\) time per query. Since there are \(Q\) queries, the overall time complexity is \(O(NQ)\). Given the constraints \(N, Q \le 10^5\), this would require around \(10^{10}\) operations, which exceeds the time limit.

Efficient Approach

By organizing index (occurrence position) information — specifically, where each word \(T\) appears — in advance, we can count occurrences quickly.

For example, if the titles are [apple, orange, apple, grape, apple], gathering the positions where apple appears gives the list [1, 3, 5]. Then, for a query like “How many apples are there between the 2nd and 4th positions?”, we just need to count the elements in the list [1, 3, 5] that satisfy \(2 \le \text{index} \le 4\).

This operation of “counting the number of elements within a specific range in a sorted list” can be performed efficiently using binary search.

Algorithm

1. Preprocessing:
   • Prepare a dictionary (hash map) where each title is a key and the value is a list of indices where that title appears.
   • Since we add indices while scanning through the books in order, the index list for each title is naturally in ascending (sorted) order.
2. Query Processing:
   • Retrieve the index list corresponding to the title \(T\) to search for.
   • Use binary search (the bisect module in Python) to find the following two values:
     • idx_R: The number of elements in the list that are \(R\) or less (bisect_right)
     • idx_L: The number of elements in the list that are less than \(L\) (bisect_left)
   • idx_R - idx_L gives the number of indices within the range \([L, R]\).

Complexity

• Time Complexity: \(O((N + Q \log N) \times |S|)\)
  • Preprocessing takes \(O(N \times |S|)\) (where \(|S|\) is the maximum string length, 10).
  • Each query requires binary search, taking \(O(\log N \times |S|)\).
  • Even when \(N, Q = 10^5\), this comfortably fits within the time limit.
• Space Complexity: \(O(N \times |S|)\)
  • Memory proportional to the total number of books is consumed to store all word indices.

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) are large, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input().

• Using Binary Search: bisect_left returns “the first position of an element greater than or equal to the specified value,” and bisect_right returns “the first position of an element strictly greater than the specified value.” By combining these, we can compute the number of elements within a specific range in \(O(\log N)\).

• Non-existent Words: If the query word \(T\) has never appeared, the key may not exist in the dictionary, so this case must be handled appropriately (by returning 0).

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.