Задача с собеседования в Яндекс
Дается массив 'a' длины n.
Даются запросы вида l, r на который вы должны вывести Yes, если подотрезок [l, r] отсортирован по неубыванию и No, иначе.
То есть вывести Yes, если a[l] <= a[l + 1] <= a[l + 2] <= .. < = a[r], иначе No.

Решение:
Если вам в голову пришла сортировка то я вас огорчу. Если сортировать теряется порядок, к тому же занимает n * log(n) времени.

Давайте создадим массив pref, где pref[i] = 1 если a[i - 1] <= a[i], и 0 иначе.
Давайте посчитаем префикс сумму от pref. Благодаря этому мы можем узнавать сколько знаков '<=' на подотрезке [l, r] за O(1).
Т.е выводим Yes, если pref[r] - pref[l] = r - l. Таким образом мы можем отвечать на запросы за O(1).

Псевдокод в комментариях: