Задача на деревья отрезков (наверное)

[Skeptic]

milos в сообщении #848292 писал(а):

Дана полоса из N клеток. На вход поступают запросы - закрасить клетку с номером $i$. Нужно определить после какого запроса есть x закрашенных подряд клеток. Например:
$N = 5, x = 3 $, красим клетки $1, 5, 4, 3, 2$ - после 3его запроса с 3 по 5ую клетку закрашены. Как можно решить эту задачу, не пробегая по массиву при каждом запросе? Как можно применить деревья отрезков для такой задачи?

При очередном закрашивании может появиться только один новый , закрашенный интервал клеток. Чтобы его выявить достаточно просмотреть соседние клетки. Хранить интервалы можно в списке или массиве.

[kp9r4d]

Skeptic в сообщении #848553 писал(а):

При очередном закрашивании может появиться только один новый , закрашенный интервал клеток. Чтобы его выявить достаточно просмотреть соседние клетки. Хранить интервалы можно в списке или массиве.

А как его длину узнавать?

[Skeptic]

Надо перебрать окрашенные клетки в обе стороны и подсчитать их число. Окрашенный интервал можно записать парой значений (<начало интервала>,<длина интервала>).

[kp9r4d]

Ну так-то ненамного лучше полного моделирования выйдет. Ведь по сути если красить сначала клетку 1, потом 2, потом 3, ... То нам придётся выполнить $O(N)$ операций сравнения за запрос и асимптотика будет $O(NM)$, или я неправильно вашу идею понял?

[Skeptic]

При полном переборе найдутся все существующие интервалы, и дополнительно придётся среди них искать последний.

[kp9r4d]

Skeptic в сообщении #849461 писал(а):

При полном переборе найдутся все существующие интервалы, и дополнительно придётся среди них искать последний.

Последний интервал может «расти» в длине и, таким образом, проверка всех остальных интервалов начиная с какого-то шага начнёт быть пренебрежительно несущественна, по сравнению с вычислением длины последнего.

[frankenstein]

Воспользуйтесь SQRT-декомпозицией.
Она позволит обрабатывать запросы за время $O(\sqrt{n})$
Тем более она проста в реализации чем RB-tree или Дерево отрезков.