Как восстановить саму последовательность в LIS (наибольшей возрастающей подпоследовательности)?
Умею считать длину LIS за $O(n \log n)$ через lower_bound по массиву хвостов. Но как при этом восстановить саму подпоследовательность? С наивным $O(n^2)$ ДП восстановление понятно через массив предков, а вот в варианте за $O(n\log n)$ хвосты «перезаписываются» и я теряю связь.
2 ответа
В $O(n\log n)$ хранишь не сами значения, а индексы: tails[len] = индекс элемента, на котором заканчивается возрастающая подпоследовательность длины len+1 с минимально возможным хвостом. Дополнительно ведёшь prev[i] — индекс предыдущего элемента в LIS, оканчивающейся в i.
int n;
vector<int> a, tails, prev_(n, -1);
// tails хранит ИНДЕКСЫ
for (int i = 0; i < n; ++i) {
// позиция, куда встаёт a[i] (строго возрастающая -> lower_bound)
int pos = lower_bound(tails.begin(), tails.end(), a[i],
[&](int idx, int val){ return a[idx] < val; }) - tails.begin();
if (pos > 0) prev_[i] = tails[pos - 1];
if (pos == (int)tails.size()) tails.push_back(i);
else tails[pos] = i;
}
// восстановление: с конца длиннейшей
vector<int> lis;
for (int cur = tails.back(); cur != -1; cur = prev_[cur])
lis.push_back(a[cur]);
reverse(lis.begin(), lis.end());
Время $O(n \log n)$, память $O(n)$. Главное — prev_[i] фиксируем в момент вставки a[i], ссылаясь на текущий tails[pos-1]; позже tails может перезаписаться, но prev_ уже «заморожен» и ведёт по корректной цепочке.
Тонкость про строгое vs нестрогое возрастание: для строго возрастающей LIS — lower_bound (вытесняем равный). Для неубывающей (допускаются равные) — upper_bound. Перепутаешь — получишь WA на тестах с повторами.
И да, восстановленная последовательность — одна из оптимальных; их может быть несколько. Если в задаче нужна лексикографически минимальная/конкретная — добавляются доп. условия при выборе prev_.