В детстве мне очень нравилась задача 1147 с тимуса statements. Нравилась в первую очередь тем, что я знал кучу решений, но никак не мог придумать ни одного быстрее, чем за N². Сейчас у меня наконец появились мысли, как решать эту задачу за NlogN.

Обобщим сперва задачу, чтобы асимптотику оценивать только через N: пусть A, B < 10⁹, color < 10⁶

Я знаю следующие решения, все они используют сжатие координат:

1. Квадродерево за O(N²)

2. Решение одномерной задачи деревом отрезков за O(NlogN) => O(N² logN)

3. Решение одномерной задачи проходом слева направо с кучей за O(NlogN) => O(N² logN)

4. Решение одномерной задачи с помощью СНМ за O(N) => O(N²) [здесь в оценке я опускаю обратную функцию Аккермана]

5. Новое: Решение за O(NlogN) [использует разделяй и властвуй по X и сжатие координат при переходе к подзадаче].

Если кто-то знает что-то еще, расскажите, пожалуйста, в комментариях, мне это будет очень интересно :-)

Самое короткое и быстрое из того, что я сдавал на тимус — решение [4].

Решение [5] пришло в голову буквально только что..

Хочется его записать. Чтобы не забыть :-)

А всем, кто читает этот текст, предлагается проверить на наличие ошибок и понятность описания.

Решение:

1. Прямоугольник = отрезок [X1..X2] и операция на отрезке "присвоить отрезку [Y1..Y2] цвет C в момент времени T".

2. У нас N прямоугольников, значит, после сжатия координат у нас не более 2N элементарных промежутков по X и по Y. Обозначим количество различных X-ов за M. Для всех M различных X-ов мы хотим получить раскраску столбца (вернее посчитать количества цветов).

3. Используем идею разделяй и властвуй, обработаем сперва первую половину X-ов, затем вторую. Алгоритм = рекурсивная функция go.

4. Общее состояние рекурсии: go( [xL..xR], column, rectangles ). [xL..xR] — отрезок X-ов, который мы сейчас обрабатываем, column — текущая раскраска всей полоски [xL..xR], rectangles — запросы-прямоугольники, которые я еще не обработал. Изначально [xL..xR] = [0..M-1], column = [0,0,0 ... 0], rectangles = все запросы.

5. Первым делом "go" разбивает rectangles на 3 группы: "не пересекается с [xL..xR]", "целиком покрывает [xL..xR]", "пересекает [xL..xR]". 1-ю группу можно выкинуть. 2-й группой перекрасить как-то column. А 3-ю группу будем передавать вниз в рекурсию.

6. Второе, что делает "go": сжатие координат. Да, каждый раз происходит новое сжатие координат.

7. За [5] и [6] я добился того, что column состоит из O(Len) элементарных клеток, и массив rectangles содержит O(Len) элементов, где Len — длина отрезка [xL..xR]. Теперь можно сделать два рекурсивных вызова. Решение закончилось.

8. Оценим время работы: T(K) = T(K/2) + T(K/2) + [5-перекрасить] + [6-сжатие-координат]. Если все координаты у меня от 0 до K-1, то сжатие координат работает за O(K). [5-перекрасить] — перекрашивание массива column, этим я занимаюсь в пункте [5]. По сути это решение одномерной задачи (см. список решений одномерной задачи). Используя СНМ, я получаю время O(Kα), где α — обратная функция Аккерамана. Итого: T(K) = 2T(K/2) + O(Kα). T(K) = O(KlogKα).

P.S. Это решение просто переиспользует все ту же мою любимую идею из dynamic-connectivity

UPD1: Михаил Колупаев верно подсказывает, что в [7] ошибка. Правильная версия такова: количество элементарных клеток = O(rectangles), а суммарное количество rectangles по всем 2M состояниям рекурсии = O(NlogN), т.к. каждый прямоугольник также, как и в дереве отрезков, присутствует только в O(logN) вершинах.

UPD2: Ошибка Я попробовал это все реализовать. Выяснилась отличная ошибка. В [6] сжатие координат не работает, т.к. уже покрашенная область имеет дурацкое свойство — у каждой клетки свое время покраски. Итог: алгоритма работающего за NlogN таки нет =((( у меня осталась только старая, уже проверенная идея, за Nlog³N.