Помимо прочего, можно создавать сложные задачи так: рассматриваем простую задачу в качестве запроса и пытаемся найти алгоритм, способный решить ее быстрее, чем наивное решение. Задачи такого типа обычно появляются в OI контестах, как правило, они решаются структурами данных.
Давайте попробуем придумать такую задачу. Например, возьмем «Задачу о подсчете расстояния Хэмминга»: для двух бинарных строк s и t одинаковой длины, расстояние Хэмминга между ними равняется количеству позиций, в которых их соответствующие символы различны. Например, расстояние Хэмминга между «00111» и «10101» равняется двум (различные символы выделены жирным).
Давайте используем задачу о расстоянии Хэмминга как запрос: вам даны две строки, a и b, и несколько запросов. Каждый запрос будет иметь следующий вид: каково расстояние Хэмминга между двумя строками ap1ap1 + 1...ap1 + len - 1 и bp2bp2 + 1...bp2 + len - 1?
Обратите внимание, что в этой задаче строки нуль-индексированные, иными словами, s = s0s1... s|s| - 1.
В первой строке записана строка a (1 ≤ |a| ≤ 200000). Во второй строке записана строка b (1 ≤ |b| ≤ 200000). Каждый символ обеих строк равен либо «0», либо «1».
В третьей строке записано целое число q (1 ≤ q ≤ 400000) — количество запросов. В каждой из следующих q строк записано по три целых числа: p1, p2 и len (0 ≤ p1 ≤ |a| - len; 0 ≤ p2 ≤ |b| - len), эти числа являются параметрами текущего запроса.
Выведите q целых чисел — ответы на запросы.
101010
11110000
3
0 0 3
2 3 4
5 7 1
1
1
0
10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20
5
4
3
5
13
| Codeforces Round 270 |
|---|
| Закончено |
