Ответ 1
Да, это можно сделать в O (log n), даже если вы должны отвечать на запросы в Интернете. Однако для этого требуются довольно сложные методы.
Во-первых, разрешите следующую задачу: задайте массив, ответьте на запросы формы "сколько чисел <= x есть внутри индексов [l, r]". Это делается с помощью структуры, подобной сегменту, которая иногда называется деревом сортировки слияния. Это в основном дерево сегментов, где каждый узел хранит отсортированный подмассива. Для этой структуры требуется O (n log n) память (потому что есть log n уровней, и для каждого из них требуется сохранение n чисел). Он также встроен в O (n log n): вы просто переходите снизу вверх и для каждой внутренней сортировки вершин сортируют списки своих дочерних элементов.
Вот пример. Скажем, что 1 5 2 6 8 4 7 1 - исходный массив.
|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|
Теперь вы можете отвечать за эти запросы в O (log ^ 2 n раз): просто сделайте запрос запроса к дереву сегментов (обход узлов O (log n)) и сделайте двоичный поиск, чтобы узнать, сколько чисел <= x есть в этом узле (дополнительно O (log n)).
Это может быть ускорено до O (log n) с использованием метода Fractional Cascading, что в основном позволяет выполнять двоичный поиск не в каждом узле, а только в корне. Однако достаточно сложно описать это сообщение.
Теперь вернемся к исходной проблеме. Предположим, у вас есть массив a_1,..., a_n. Создайте другой массив b_1,..., b_n, где b_i = индекс следующего вхождения a_i в массиве или ∞, если это последнее вхождение.
Пример (1-индексированный):
a = 1 3 1 2 2 1 4 1
b = 3 ∞ 6 5 ∞ 8 ∞ ∞
Пусть теперь числа в [l, r]. Для каждого уникального номера мы будем считать его последнее вхождение в сегменте. С понятием b_i вы можете видеть, что появление числа является последним, если и только если b_i > r. Таким образом, проблема сводится к "количеству чисел> r в сегменте [l, r]", которая тривиально сводится к тому, что я описал выше.
Надеюсь, поможет.