Помимо прочего, можно создавать сложные задачи так: рассматриваем простую задачу в качестве запроса и пытаемся найти алгоритм, способный решить ее быстрее, чем наивное решение. Задачи такого типа обычно появляются в OI контестах, как правило, они решаются структурами данных.
Давайте попробуем придумать такую задачу. Например, возьмем «Задачу о подсчете расстояния Хэмминга»: для двух бинарных строк s и t одинаковой длины, расстояние Хэмминга между ними равняется количеству позиций, в которых их соответствующие символы различны. Например, расстояние Хэмминга между «00111» и «10101» равняется двум (различные символы выделены жирным).
Давайте используем задачу о расстоянии Хэмминга как запрос: вам даны две строки, a и b, и несколько запросов. Каждый запрос будет иметь следующий вид: каково расстояние Хэмминга между двумя строками ap1ap1 + 1...ap1 + len - 1 и bp2bp2 + 1...bp2 + len - 1?
Обратите внимание, что в этой задаче строки нуль-индексированные, иными словами, s = s0s1... s|s| - 1.