http://acm.math.spbu.ru/~sk1/mm/lections/mipt2014-sqrt/mipt-2014-burunduk1.pdf

Такое точно решается корневой декомпозицией, правда временная сложность хуже получается.

не так понял условие, ниже нормальное решение.

Решение за O(log^3(N)) на запрос.

Сожмем все входные данные. Храним дерево фенвика для каждого X. В каждой вершине дерева фенвика храним неявное дерево отрезков. В каждой вершине неявного дерева отрезков храним двоичное дерево поиска (например декартово дерево). Для каждого числа поддерживаем next[i] — позиция следующего такого же числа как и a[i] (или n+1 если такого нет) (как и в случае количество различных элементов на отрезке).

Запрос изменения (i, x): в дереве фенвика на суфиксе сделаем del(i,next[i]) — удалим из всех деревьев отрезков next[i], затем a[i]=x и add(i,next[i]) — добавим во все деревья отрезков наше число. Можно сказать что бы удаляем\добавляем (i, next[i]) в каждом дереве отрезков на суффиксе(но посещая при этом логарифм позиций так как это фенвик).

Запрос количества (l, r, x): присвоим x позицию в сжатом массиве, теперь ответом будет get(x, l, r) на префиксе в дереве фенвика в каждом дереве отрезков находим на отрезке с l по r количество чисел больших x (с помощью двоичного дерева поиска в каждой вершине).

Если решать задачу как "давайте поддерживать массив next и отвечать на 3D-запрос L <= i <= R, a[i] <= x, next[i] > R", то, видимо, для меняющегося массива a ничего сильно лучше O(log³n) не получится.

Вот, что гуглится:

1. Для не меняющегося массива 3D-запрос умеют за O(logn). Это вроде классика.
   Можно почитать, например, в лекциях MIT

2. Для меняющегося массива уже с 2D-запросом есть проблема преодолеть барьер O(log²n) => если сверху навесить дополнительное дерево отрезков, для 3D-запроса будет как раз O(log³n).

Подробно про 2D-запрос для меняющегося массива.

Гуглить нужно по словам "dynamic orthogonal range", а ещё точнее "dynamic orthogonal range counting". Есть много статей на тему "reporting" -- вывести все точки, но нас интересует только "counting" -- посчитать количество.

На выходе получаются две статьи.

a) The Cell Probe Complexity of Dynamic Range Counting (2012)
Даёт нижнюю оценку O((logn / loglogw)²) на weighted orthogonal range counting (т.е. найти не количество, а сумму)

b) Space Efficient Data Structures for Dynamic Orthogonal Range Counting [pdf] [html] (2013)
Даёт структуру данных с O(n) памяти и O((logn / loglogn)²) времени на оба запроса -- подсчёт и изменение.

P.S. Ну а за log³n с одной стороны очень медленно, с другой вроде не сложно -- дерево деревьев деревьев.

Если нужно, чтобы и код короткий, и работало быстро, есть решение за O(N^0.5) без лишних логов.
Это должно быть даже чуть быстрее log²N при N ≤ 300 000.

Короткое описание решения: дерево отрезков по i, внутри корневая по запросам, внутри корневая по a[i] и next[i].

Подробно:

1. Когда мы научимся отвечать за n^0.5 на запрос посчитать i: a[i] <= x, next[i] > R, то, поместив такую структуру в каждую вершину дерева отрезков по i, сможем считать i: L <= i <= R, a[i] <= x, next[i] > R за N^0.5 + (N / 2)^0.5 + (N / 4)^0.5 + ... = O(N^0.5). Теперь научимся отвечать на 2D запрос, n  –  размер конкретной вершины ДО, N  –  размер исходного массива.
   
   

2. Если бы массивы a и next не менялись, можно было бы решать так. Отсортируем пары <a[i], next[i]> сперва по ключу a[i] (массив X), затем по ключу next[i] (массив Y). Теперь каждая пара однозначно задаётся позициями в X, Y  –  x_i, y_i. Важно, что это числа из [0, n), все x_i различны, все y_i различны. Нарисуем точки x_i, y_i на плоскости, разобьём квадрат n × n на клетки k × k, где k = n^0.5. Клетки образуют двухмерный массив размера (n / k) × (n / k), на котором можно предподсчитать двухмерные частичные суммы F. Когда приходит запрос на подсчёт i: a[i] <= A, next[i] > R, за O(logn) бинпоиском находим позиции A в X и R в Y, обозначим их x, y. За O(n^0.5) округляем x и y к ближайшим числам кратным k. За O(1) обращаемся к F.
   
   

3. Операция a[i] = x меняет две пары <a[i], next[i]>. Перестраивать структуру не будем, вместо этого добавим в стек отложенных операций две старые точки со знаком -1 и две новые со знаком +1.
   
   

4. Когда длина стека станет больше 2n^0.5, перестроим структуру за O(n)  –  у нас есть отсортированный старый массив, нужно n^0.5 элементов удалить, n^0.5 элементов добавить.
   
   

5. Построение структуры в одной вершине ДО занимает O(sort + n), где sort = n, так как можно померджить детей. Итого ДО корневых строится за O(NlogN) и весит O(NlogN).

P.S. Или без лишних логов можно как-то проще?

deleted