Испытание

Заметим, что после применения операции побитового «ИЛИ» элемента массива fi с числом x в fi могли измениться только те биты, на месте которых в x стоят единицы (то есть нулевые биты в fi, стоящие на позициях, соответствующих единицам в числе x, стали единицами). После применения операции побитового «И» с числом x в fi могли поменяться только те биты, на месте которых в x стоят нули (единичные биты в fi становятся нулями). То есть при операции «ИЛИ» имеет смысл рассматривать только единичные биты из x, а при операции «И» — на нулевые биты из x , потому что только такие биты «затрагивают» какие-то биты в fi при применении той или иной операции.

Теперь заметим, что если операция «затрагивает» какие-то биты, то после ее применения эти биты во всех числах станут одинаковыми и далее будут изменяться синхронно, и последующие изменения какого-то из этих битов не будут влиять на ответ, так как изменение всех единиц, стоящих на k-ом месте в каждом числе, на ноль будет означать лишь вычитание числа 2k из каждого числа, что не влияет на количество неубывающих отрезков (а изменение всех нулей на единицу, соответственно, прибавление некоторой одной и той же степени двойки к каждому числу). Из всего вышеизложенного можно сделать вывод, что если бит с номером k в каждом числе из массива был «затронут» какой-то операцией, мы не будем обращать внимание на последующие «затрагивания» этого бита. Соответственно, будем поддерживать некую переменную changed, хранящую в своем двоичном представлении единицы на позициях тех битов, которые хоть раз были «затронуты» какой-то операцией. И если «затрагиваемые» текущей операцией биты являются подмаской числа changed, ответ на текущем запросе будет равен ответу на предыдущем. Если же «затрагиваемые» биты не являются подмаской changed, значит какие-то биты в числах из массива еще не достигли «синхронного» состояния, и ответ должен быть пересчитан. Ответ пересчитывается за длину массива. Ответ в худшем случае будет пересчитан столько раз, сколько битов содержится в двоичном представлении чисел в массиве (в этом случае каждая операция «затрагивает» только один новый бит). Поэтому асимптотика — .