242A - Игра в монетку

Эта задача решалась очень просто: достаточно было двумя вложенными циклами по i и по j (a ≤ i ≤ x, b ≤ j ≤ y) перебрать всевозможные исходы игры и выделить среди них те, в которых i > j. Такие пары и составляют ответ. Время – O(x·y).

242B - Большой отрезок

Для начала заметим, что ответ всегда однозначный, потому что если существует отрезок номер i, который покрывает отрезок номер j, то отрезок j никак не может покрывать отрезок i. Единственный случай, когда такое возможно, — это когда отрезки i и j совпадают, однако по условию в наборе нет одинаковых отрезков. Заметим, что ответ должен покрывать самую левую из всех точек всех отрезков, и аналогично, самую правую из всех точек. Таким образом, надо найти эти точки линейным проходом: L = min(l_i), R = max(r_i), и найти номер отрезка [L, R], либо вывести  - 1, если его нет в заданном множестве. Время --– O(n).

242C - Путь короля

Самое главное для решения этой задачи – заметить, что суммарная длина всех отрезков не превосходит 10⁵. Используя этой свойство, мы можем занумеровать все разрешенные клеточки, и найти кратчайший путь с помощью обхода в ширину. Проще всего занумеровать клеточки используя ассоциативный массив (например, map в C++). Время –-- O(n·log(n)).

242D - Спор

Обозначим через b_i текущее число на счетчике номер i. Решать задачу будем следующим образом: возьмем любой счетчик i, такой, что b_i = a_i, и нажмем на соответствующую кнопку. Алгоритм прекратим тогда, когда такого i не найдется. Поймем, что этот алгоритм на самом деле решает задачу. Нам необходимо объяснить несколько условий:

1. Почему после конца алгоритма состояние будет выигрышным для Валеры? Потому что не будет существовать такого i, в котором b_i = a_i, а иначе мы бы нажали на кнопку.

2. Почему алгоритм не будет нажимать одну и ту же кнопку дважды? Потому что мы нажимаем кнопку i, только если b_i = a_i, и сразу же, как мы нажмем, число b_i увеличится, и равенство больше никогда не выполнится.

3. Почему этот алгоритм можно реализовать за приемлемое время? Потому что из условия 2 следует, что алгоритм сделает не более n нажатий, которые суммарно приведут не более чем к n + 2·m прибавлениям к числам. Для того, чтобы быстро находить те числа, в которых b_i = a_i, можно воспользоваться очередью: каждый раз, когда мы изменили число b_i, и оно стало равным a_i, то закидывать в очередь i. Несложно понять, что одно и то же число не может быть закинуто в очередь дважды.

Из алгоритма следует, что ответ всегда существует, а значить выводить  - 1 никогда не нужно было. Время – O(n + m).

242E - XOR на отрезке

Запишем числа a₁, a₂, ..., a_n в виде таблицы n × 20 где b_i, j равно j-ому биту в i-ом числе. Тогда сумма на отрезке [l, r] равно что равно , то есть мы можем перебрать номер бита j, найти в скольких числах этот бит равен 1, и прибавить к ответу (количество)·2^j.

Для эффективной реализации воспользуемся 20-ю деревьями отрезков по сумме, каждый из которых будет соответствовать одному из битов (то есть одному из столбцов таблицы b_i, j). Тогда операции можно переформулировать:

1. подсчет суммы эквивалентен нахождению количества единиц с l по r.

2. операция "xor" эквивалентна изменению всех бит c l по r на противоположные (то есть 0 меняется на 1, а 1 – на 0).

Первая операция выполняется для всех номеров бит, вторая – только для тех номеров бит, в которых у числа из входных данных стоит 1.

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

Время — O(m·log(n)·20).