История изменений
Исправление AntonI, (текущая версия) :
всяко нужно 2 переменные для задания отрезка(связности)
Напиши объект непрерывного интервала и храни такие штуки в set. В переменной держи самый длинный интервал. Но помни, что интервалы придется иногда сшивать.
На питоне set куцый в смысле интерфейса, это лучше на плюсах делать.
Формально будет все тот же O(N log N), но на практике скорее всего O(N log M) где M много меньше N, от данных зависит. Для 5e4 элементов можно в сторону битовой маски подумать, или тупо взять вектор тех же самых интервалов длины 5e4.
Дальше нюансы реализации, но все ОЧЕНЬ сильно зависит от данных. В данных ТС максимальный int 25000 например;-)
Исправление AntonI, :
всяко нужно 2 переменные для задания отрезка(связности)
Напиши объект непрерывного интервала и храни такие штуки в set. В переменной держи самый длинный интервал. Но помни, что интервалы придется иногда сшивать.
На питоне set куцый в смысле интерфейса, это лучше на плюсах делать.
Формально будет все тот же O(N log N), но на практике скорее всего O(N log M) где M много меньше N, от данных зависит. Для 5e4 элементов можно в сторону битовой маски подумать, или тупо взять вектор каких нить интов длины 5e4.
Дальше нюансы реализации.
Исправление AntonI, :
всяко нужно 2 переменные для задания отрезка(связности)
Напиши объект непрерывного интервала и храни такие штуки в set. В переменной держи самый длинный интервал.
На питоне set куцый в смысле интерфейса, это лучше на плюсах делать.
Формально будет все тот же O(N log N), но на практике скорее всего O(N log M) где M много меньше N, от данных зависит. Для 5e4 элементов можно в сторону битовой маски подумать, или тупо взять вектор каких нить интов длины 5e4.
Дальше нюансы реализации.
Исходная версия AntonI, :
всяко нужно 2 переменные для задания отрезка(связности)
Напиши объект непрерывного интервала и храни такие штуки в set. В переменной держи самый длинный интервал.
На питоне set куцый в смысле интерфейса, это лучше на плюсах делать.
Формально будет все тот же O(N log N), но на практике скорее всего O(N log M) где M много меньше N, от данных зависит. Для 5e4 элементов можно в сторону битовой маски подумать.
Дальше нюансы реализации.