Могу рассказать самое красивое решение

Просто я не понимаю как). Ну мы посчитали для каждого блока сколько на нем различных элементов. Но как нам  сmerge'ить все блоки  и концы быстро

Там немного не так. Нужно посчитать динамику dp[i] = j, j < i, где j - ближайшая к i слева позиция такая что arr[i] == arr[j].

Теперь обработаем все запросы в порядке возрастания правой границы. Будем поддерживать корневую декомпозицию на префиксе:

for (int r = 1; r <= n; r++)
    // обновим декомпозицию следующим образом:
    x[r]++    
    if (dp[r] != -1) x[dp[r]]--;
    // теперь отвечаем на все запросы с правой границей равной r
    // пусть запрос {l, r}, тогда ответ: сумма в корневой декомпозиции от l до r

О! Спасибо. Тогда это и ДО по идее за log n можно сделать

То есть, в массиве x мы отмечаем единицей только последнее вхождение каждого элемента на префиксе. И лучше фенвиком, конечно

Есть еще такое решение. Посчитаем dp[i] = j - ближайшая справа от i позиция такая что arr[i] == arr[j].
Тогда ответ на запрос [L, R] - количество элементов dp[i] > R на отрезке. Построим ДО на элементах.

Пусть элементы массива лежат из диапазона 0 <= dp[i] <= n. Изначально в корне дерева лежит весь массив dp в исходном порядке и корень отвечает за диапазон [0, n]. Посчитаем середину отрезка: mid = (0 + n) / 2 и в корне создадим дополнительный массив b[i] = bool(dp[i] >= mid), то есть, b[i] = 1, если dp[i] >= mid, и 0 иначе. Теперь посчитаем префикс суммы для массива b: s[i] = s[i-1] + b[i]. Все элементы, dp[i] < mid, отправим в левое поддерево, а dp[i] >= mid - в правое, сохраняя порядок.

Построение за O(n log(n)) памяти и времени.

Как отвечать на запрос за O(log(n)) теперь? Если уметь отвечать за O(1) в каждом узле, то это будет O(log(n)).

Пусть запрос {L, R, X}: сколько элементов dp[L..R] >= X. Тогда если X <= mid, то это, то это s[R] - s[l-1] + запрос к левому поддереву что-то вроде {L-S[L], R-S[R], X}, иначе x > mid и продолжаем с правым поддеревом, пересчитывая L и R за O(1).

Благодарю!

Кажется,  придумал простое деревянное решение

В смысле,  на деревьях поиска

можете показать, откуда задача?

Вообще задача с первого дня региона Всеросса 2018-2019, там для окончательного решения надо научиться это делать.
https://codeforces.com/gym/102086
Задача 3

ru-olymp-regional-2019-solutions.pdf

ага,  ну да, оффлайн-решение
любая структура, умеющая хранить уникальные элементы, добавлять и отвечать на вопрос "сколько всего элементов в интервале"

Первый проход - заводим такую структуру, N списков и хэшмапу с предыдущим вхождением числа, проходим по массиву. Если предыдущего вхождения элемента не было - ложим его номер в структуру, если было на позиции i -  в i'й список

Дальше последовательно для всех позиций
Если есть отрезки, начинающиеся на этой позиции -  делаем запрос к структуре, сколько всего у нас элементов внутри отрезка, получаем ответ для отрезка.
После чего (в любом случае) слаживаем элементы из i-го списка в структуру

Можете помочь плиз с алгоритмом? Это задача несложная, надо решить за час, но я до конца не понимаю. Ну очевидно цикл от 0 до n, внутри его цикл по квадратам от 0 до i. Правда это очень медленно работает и не совсем понятно что делать с этими квадратами(

Похоже на задачу о рюкзаке...

Или стоп, цикл от 0 до N вообще нужен?

Не особо, хотя возможно и да

Но я не увидел связи