Научимся отвечать на запросы без модификаций массива. Для начала положим, что zi не убывают. Будем хранить новый массив t. Для i-го запроса, он будет выглядеть так:
ti = 0, если ai > zi,
ti = 1, если ai ≤ zi.
Как переходит от i-го массива к i + 1 понятно — нужно в нужных местах добавить 1. Чтобы отвечать на запрос от l до r, нам необходимо посчитать сумму на отрезке в массиве t. Чтобы делать это быстро, будем хранить t как дерево отрезков.
Теперь избавимся от ограничения на zi. Для этого сделаем наше дерево отрезков персистентным. Большему zi должна соответствовать большая версия, поэтому чтобы построить такое дерево отрезков, отсортируем исходный массив ai и занесем в персистентное дерево отрезков. Для всех возможных значений zi запомним максимальный номер версии, запрос к которой будет соответсвовать запросу li, ri, zi. Будем хранить номер в массиве v. Отвечать на запросы мы научились.
Теперь посмотрим, что происходит, когда мы делаем операцию инкремента чисел равных x. Если до инкремента запросу l, r, x соответсвовал запрос в дереве отрезков с версией v[x], то после инкремента ответ можно получить в v[x - 1]. Для чисел не равных x не поменялось ничего. Поэтому, чтобы выполнить операцию инкремента, нам необходимо сделать v[x] = v[x - 1].
Сложность по времени: , по памяти: