1466: Запити
Перегляд у форматі PDFОсь одна із задач Василька, яка уже два тижні йому не піддається. Завтра у нього День народження! Давайте зробимо Васильку інтелектуальний подарунок - напишемо швидкий код, який вирішить його проблему.
Отже, задається N рядків, пронумерованих від 1 до ~N~.
Ваша програма повинна оперативо відповісти на ~Q~ запитів. Запит має вигляд: ~l, r, S~.
Для кожного запиту програма повинна знайти, скільки разів рядок ~S~ зустрінеться на проміжку ~[l, r]~.
Формат вхідних даних
Перший рядок містить ціле число ~N~ ~(1 \le N \le 100000)~ - кількість рядків.
Далі ідуть ~N~ рядків.
Наступний рядок містить ~Q~ ~(1 \le Q \le 100000)~ - кількість запитів.
Далі ідуть рядки із запитом: ~l, r, S~ ~(1 \le l \le r \le N)~.
Всі рядки мають довжину від 5 до 10 символів.
Формат вихідних даних
Для кожного запиту в окремому рядки вивести відповідь
Приклад вхідних даних
3
abc
def
abc
3
1 2 abc
1 3 abc
1 2 hgj
Приклад вихідних даних
1
2
0
Коментарі
Додайте часу на Python, будь ласка (або скажіть, що можна написати ефективніше рішення цією мовою) Просто аналогічне рішення на С++ набирає 100/100
Добавив...