Архив V Международной Жаутыковской олимпиады по информатике

В обратном порядке:
Горная трасса.
Идея правильная. Самое просто решение на основе этой идеи выглядит так. Можно заметить, что можно убрать в этой идее условие "для каждой вершины одинаковая высота". А именно - все горизонтальные отрезки, вне зависимости от того, есть ли под ними какие вырезы или нету, сложим в один список. И будем на каждой итерации брать минимальный отрезок. Теперь поймём, что "плохой" отрезок, т. е., который не является сплошным, то есть под которым есть какие-то провалы, мы не возьмём раньше, чем закроем все провалы под ним - так как длина каждого из провалов меньше чем длина самого отрезка. Поясню: в такой картинке:

*       *
** *  *
У нас будет четыре отрезка. Один на самом верхнем слое, один на среднем и два на нижнем. Мы их положим в список в порядке возрастания, и тогда, понятно, отрезок со среднего слоя мы не возьмём раньше, чем два отрезка с нижнего, поэтому всё корректно.
А теперь достаточно понять, что физически ничего класть в списки не надо. Можно применить идею из сортировки подсчётом. Посчитаем количество отрезков длины 1, длины 2, ... На каждой итерации либо будем брать все отрезки длины i и переходим к отрезкам длины i + 1, либо считаем максимальное количество, какое мы сможем взять за O(1) и вываливаемся.
Если после этого пожать координаты, то станет ясно, что таких отрезков (которые в реальности будут "прямоугольничками") может быть не более O(n). Получается простое до невозможности решение за O(nlogn).

Биороботы. Тут всё хитро. Есть идея, как решать динамикой по поддеревьям за O(nm^2)?

Xor. Расскажу не моё решение, а решение Паши Кунявского - оно проще для понимания. Моё развивает идею с битовой записью.
Сначала лемма. Множество [a;b] после применения ксора с каким-то числом t переходит в объединение не более чем 32 отрезка. То есть проверить число на принадлежность {t ^ x | x [a; b] можно проверив его на принадлежность каждому из этих 31 отрезков. Например, отрезок [1; 6] переходит в объединение отрезков [1; 4] и [7; 8] после ксора с тройкой.
Посчитаем xor-суммы на префиксах. Обозначим их за S[i].
Теперь будем идти слева направо, поддерживая в некоторой структуре данных, например, дереве отрезков, суммы на префиксах до i-ого включительно. На этой итерации мы будем анализировать все подотрезки, заканчивающиеся в i-ом элементе. Что значит, что xor(A[j], A[j+1], ... , A[i]) [x; 2³²)? Значит, что S[j - 1] ^ S[i] в том отрезке. Это значит, что S[j - 1] в объединении тех 32 отрезков, которые получаются, после применения ксора к сегменту [x; 2³²). То есть на i-ой итерации нужно посчитать количество чисел среди S[i], которые лежат в одном из этих отрезков. Это либо делается в онлайне за n log^2 n log MAX деревом отрезков (log MAX - это тот самый множитель в 32), либо сканлайном за n log n log MAX.
У жюри было решение за такую же асимптотику. К слову, у меня есть решение просто за n log MAX, я его написал на контесте, но оно шибко умное и тяжелое и я его не расскажу :-) Можно покурить мой код, если охота. Оно даёт идею, которая легко трансформируется в красивую задачу, которая, может быть, где-нибудь здесь появится в моём контесте.