Overview

Given \(N\) books on a bookshelf, for each of \(Q\) queries, we need to efficiently determine how many books within a specified range \([L, R]\) have a title matching \(T\).

Analysis

Naive Approach and Its Issues

The simplest method is, for each query, to examine every book from position \(L\) to position \(R\) one by one, checking whether its title matches \(T\). However, this approach takes up to \(O(N)\) per query, resulting in \(O(NQ)\) overall. Since both \(N\) and \(Q\) can be up to \(10^5\), this leads to up to \(10^{10}\) operations in the worst case, causing TLE (Time Limit Exceeded).

Key Insight

The essence of each query is: “How many times does a given title \(T\) appear at positions between \(L\) and \(R\) inclusive?”

If we record, for each title, the positions where it appears in ascending order, we can answer this efficiently using Binary Search.

For example, if the title "abc" appears at positions \([2, 5, 8, 12]\), and we want to find how many fall within the range \([3, 10]\):

• The first position \(\geq 3\) → \(5\) (index 1 from the left)
• The last position \(\leq 10\) → \(8\) (index 2 from the left)
• Count = \(2 - 1 + 1 = 2\) (elements at indices 1 and 2)

Using Python’s bisect_left and bisect_right, this can be computed in \(O(\log N)\).

Algorithm

1. Preprocessing: Prepare a dictionary (hash map) where each title is a key, and the value is a list of positions (1-indexed) where that title appears, stored in ascending order. Since we read the books from left to right, the order is naturally ascending.

2. Answering each query: Retrieve the position list corresponding to title \(T_j\), and use binary search to find the number of elements within the range \([L_j, R_j]\).

   • bisect_left(pos_list, L) gives the index where elements \(\geq L\) begin
   • bisect_right(pos_list, R) gives the index where elements \(> R\) begin
   • The difference yields the count within the range

3. If title \(T_j\) does not exist in the dictionary, the answer is \(0\).

Complexity

• Time Complexity: \(O(N + Q \log N)\)
  • Preprocessing to register \(N\) books in the dictionary: \(O(N)\)
  • Two binary searches per query: \(O(\log N)\) × \(Q\) queries
• Space Complexity: \(O(N)\)
  • Storing a total of \(N\) occurrence positions across all titles

Implementation Notes

• Fast Input: By reading all input at once with sys.stdin.buffer.read() and splitting into tokens with split(), I/O processing can be done efficiently even in Python.

• Fast Output: Accumulate the results of each query in a list and output them all at once with '\n'.join(out) at the end. This is significantly faster than calling print \(Q\) times.

• 1-indexed Handling: Since book positions are 1-based in the problem statement, we store them as 1-indexed in the position lists, allowing direct comparison with the \(L\) and \(R\) values from the queries.

• defaultdict(list): When a title appears for the first time, an empty list is automatically created, eliminating the need for key existence checks and making the code more concise.

  Source Code

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

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    Q = int(tokens[idx]); idx += 1
    
    # For each title, store sorted list of positions (1-indexed)
    title_positions = defaultdict(list)
    for i in range(1, N + 1):
        s = tokens[idx]; idx += 1
        title_positions[s].append(i)
    
    out = []
    for _ in range(Q):
        L = int(tokens[idx]); idx += 1
        R = int(tokens[idx]); idx += 1
        T = tokens[idx]; idx += 1
        
        if T in title_positions:
            pos_list = title_positions[T]
            count = bisect_right(pos_list, R) - bisect_left(pos_list, L)
            out.append(str(count))
        else:
            out.append('0')
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.