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

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

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

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

Нужно рассмотреть много случаев. Для школьников это не должно быть проблемой, ведь у каждого собственная тетрадка для записей :) Не бойтесь, случаев не так уж и много, а при написании решения они вообще не будут использоваться (только следствие из них).

Рассмотрим плиточку. Если плиточка пустая, то ничего интересного не произойдет, так как поворот ни на что не влияет. Поэтому посмотрим на непустую плитку. Тут на самом деле все просто. В этой плитке могли встретится:

1. Цикл и цикл — тогда поворот такой плитки уменьшает количество циклов на 1;
2. Цикл и цепочка — тогда поворот опять уменьшает количество циклов на 1, количество цепочек остается прежним;
3. Цепочка и цепочка — поворот никак не повлиял на количество циклов и цепочек;

Дан массив 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). Собственно мы получили решение за . Заметим, что слияние можем делать сразу степенями двойки, но ограничения задачи не требовали этого.

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

Во первых, избавимся от строк, которые полностью входят в другие строки. Теперь посчитаем такую метрику d(i, j) — минимальная длина строки, префикс которой является строкой s_i, а суффикс s_j. Теперь представим каждую строку как вершину графа, а ребра как склеивания этих строк. Наша задача найти кратчайший путь, такой, что все вершины мы посетим один раз. Другими словами найдем гамильтонов путь в графе. А потом просто его восстановим. Вершин всего 30, поэтому придется немного подождать, так как потребуется порядка 2^30*30 операций.

Для данных тестов можно поступить еще проще — выбирать ребра жадно.