LIS через std::set: можно ли заменить tails на множество и где подвох?
Видел реализацию LIS не через массив tails с lower_bound, а через std::set с lower_bound/erase. Это работает? И в чём подвох по сравнению с массивом — есть ли разница для строгой и нестрогой возрастающей?
2 ответа
Да, set тоже даёт LIS за O(n log n), идея та же — поддерживаем множество «хвостов». Для каждого x: ищем первый элемент >= x через set::lower_bound. Если нашли — стираем его (заменяем на x, чтобы хвост стал «лучше»); если нет — x удлиняет последовательность, просто вставляем.
// строго возрастающая LIS
set<int> s;
for (int x : a) {
auto it = s.lower_bound(x); // первый >= x
if (it != s.end()) s.erase(it);
s.insert(x);
}
int lis_len = s.size();
Сложность O(n log n) время, O(n) память. Подвох: при равных элементах set хранит уникальные значения, что естественно для строгой LIS. Размер set — это и есть длина LIS.
Главный подвох — нестрого возрастающая (неубывающая) LIS. Для неё нужно искать upper_bound (первый строго > x), а не lower_bound. Но std::set не хранит дубли, поэтому равные элементы «схлопнутся» и ты недосчитаешь длину. Для неубывающей LIS через set придётся брать multiset и upper_bound:
multiset<int> s;
for (int x : a) {
auto it = s.upper_bound(x); // первый > x
if (it != s.end()) s.erase(it);
s.insert(x);
}
Ещё set/multiset медленнее массива из-за указателей и плохой локальности — на жёстких ограничениях лучше массив tails с lower_bound/upper_bound. Восстановить саму подпоследовательность через set тоже сложнее, чем через массив индексов.