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

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

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

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

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

Дан массив a из n чисел и q запросов. Запросы двух типов:

1. 1 x — увеличить все числа x в массиве a на 1.
2. 2 l r z — посчитать, сколько чисел на отрезке от l до r не больше z.

Научимся отвечать на запросы без модификаций массива. Для начала положим, что 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].

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

Найдем все делители d_i числа m. Посчитаем f_i — количество чисел 1 ≤ j ≤ k таких, что gcd(m, j) = d[i]. По факту, мы уже умеем решать задачу при n = 1. Как получить ответ для n > 1? Давайте поймем, как получать ответ для n = 2. Пусть p_x — этотакоечисло, чтоd[p[x]] = x. Посчитаем g_k как сумму f_i·f_j таких, что gcd(m, d_i·d_j) = d_k. Собственно мы получили массив f, но для n = 2 путем слияния двух ответов для n = 1. Как получить ответ для n = 3? Сольем ответы для n = 2 и n = 1 (то есть f и g). Такое слияние мы делаем за , но если предподсчитать gcd за , то слияние можно делать за O(m). Собственно мы получили решение за . Заметим, что слияние можем делать сразу степенями двойки, но ограничения задачи не требовали этого.

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