Дано N и M (1 <= M <= 2e5) (1 <= N <= 1e5) и массив an (1 <= a[i] <= 1e6). Нужно ответить на каждый из M запросов типа "найти самый часто встречающийся элемент на отрезке l r". Если ответов несколько можно выводить любой. Как можно решить эту задачу с помощью дерево отрезков?
Зачем делать задачу с
дерево отрезков
, если можно делать сструктуры данных
.P.S. Дерево жрет на 4 раза больше памяти, чем структуры данных.
Зачем нести
бред
, если можно не нести.Он спросил как решить задачу с помощью дерево отрезков(это значит, что он хочет решить задачу с помощью дерево отрезков). А твой коммент тут не к месту.
Я не знаю как можно решить эту задачу с помощью дерево отрезков, но можно с алгоритмом MO за
Это довольно хорошо изученная задача link
А если с изменениями?
Upd: Понял, можно накапливать корень изменений, и это не повлияет на сложность.