Сложность по времени

Решим задачу для полоски. А решать такую задачу можно жадно. Ведь действительно, если мы можем поставить очередную перегородку в позициях i и i + 1, то будет не хуже, если мы поставим в i + 1. Чтобы понять, нужно ли нам ставить перегородку, будем хранить текущий OR чисел, между которыми еще нет перегородок. Если AND с очередным числом дает больше 1, то мы обязаны поставить перед этим числом перегородку.

Чтобы решить исходную задачу, нужно перебрать позицию первой перегородки. После этого, задача сводится к задаче на полоске. К сожалению, такое решение работает за квадрат, что недостаточно быстро. Но заметим забавный факт — расстояние между перегородками не будет превышать . Поэтому нам достаточно перебрать первые позиций для первой перегородки.

Сложность по времени: , по памяти: O(n).

Тут будет какое-то решение

Научимся отвечать на запросы без модификаций массива. Для начала положим, что z_i не убывают. Будем хранить новый массив t. Для i-го запроса, он будет выглядеть так:
t_i = 0, если a_i > z_i,
t_i = 1, если a_i ≤ z_i.
Как переходит от i-го массива к i + 1 понятно — нужно в нужных местах добавить 1. Чтобы отвечать на запрос от l до r, нам необходимо посчитать сумму на отрезке в массиве t. Чтобы делать это быстро, будем хранить t как дерево отрезков.

Теперь избавимся от ограничения на z_i. Для этого сделаем наше дерево отрезков персистентным. Большему z_i должна соответствовать большая версия, поэтому чтобы построить такое дерево отрезков, отсортируем исходный массив a_i и занесем в персистентное дерево отрезков. Для всех возможных значений z_i запомним максимальный номер версии, запрос к которой будет соответсвовать запросу l_i, r_i, z_i. Будем хранить номер в массиве v. Отвечать на запросы мы научились.

Теперь посмотрим, что происходит, когда мы делаем операцию инкремента чисел равных x. Если до инкремента запросу l, r, x соответсвовал запрос в дереве отрезков с версией v[x], то после инкремента ответ можно получить в v[x - 1]. Для чисел не равных x не поменялось ничего. Поэтому, чтобы выполнить операцию инкремента, нам необходимо сделать v[x] = v[x - 1].

Сложность по времени: , по памяти: