タイトルごとに本の位置のindexの(ソートされた)リストを保持することで、そのリストを二分探索することにより答えを求めることができます。

辞書の構築に \(O(N\log N)\) 、クエリごとの二分探索に \(O(\log N)\) かかることから、全体で \(O((N+Q)\log N)\) 時間でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, q;
  cin >> n >> q;
  map<string, vector<int>> d;
  for(int i=0; i<n; i++){
    string s;
    cin >> s;
    d[s].push_back(i);
  }

  for(int i=0; i<q; i++){
    int l, r;
    string t;
    cin >> l >> r >> t;
    l--;
    int ans = lower_bound(d[t].begin(), d[t].end(), r) - lower_bound(d[t].begin(), d[t].end(), l);
    cout << ans << endl;
  }
}

実装例 (Python)

from bisect import bisect_left
from collections import defaultdict

N, Q = map(int, input().split())
S = input().split()
d = defaultdict(list)
for i, s in enumerate(S):
  d[s].append(i)

for _ in range(Q):
  L, R, T = input().split()
  L = int(L) - 1
  R = int(R)
  ans = bisect_left(d[T], R) - bisect_left(d[T], L)
  print(ans)