Представим массив длины N в i-той ячейке которого будем хранить количество пассажиров уже купивших
билет и едущих от станции i к (i+1).
Будем поддерживать для такого массива RMQ (дерево максимумов) с возможностью быстрой модификации
(прибавления) на отрезке.

Теперь при обработке каждого запроса мы сначала узнаём максимум на отрезке [x; y-1], и, если он меньше
К (т.е. между каждой парой станций на маршруте существует хотя бы одно свободное место), продаём билет
и выполняем update(x, y-1, +1). Иначе отказываем в продаже билета.

Каждый из запросов getMax() и update() выполняется за O(log N) операций.
Конечная сложность алгоритма O(M * log N)

Отредактировал(а) Александр Чистяков