Как восстановить LIS за O(n log n), а не только её длину?
Длину наибольшей возрастающей подпоследовательности я умею считать за O(n log n) через lower_bound по массиву хвостов tails. Но в задаче надо вывести саму подпоследовательность, а не только её длину. Как восстановить элементы, если tails я по дороге перетираю?
for (int x : a) {
int pos = lower_bound(tails.begin(), tails.end(), x) - tails.begin();
if (pos == tails.size()) tails.push_back(x);
else tails[pos] = x;
}
// длина = tails.size(), а как достать сами элементы?
2 ответа
Идея: при обработке каждого a[i] запоминай, в какую позицию pos он попал (это длина LIS, оканчивающейся на нём, минус 1), и кто был предыдущим элементом в этой подпоследовательности. Предыдущий — это тот, что сейчас стоит в pos-1 массива хвостов. Заведи два массива: len[i] = pos и parent[i] — индекс элемента, лежащего в pos-1.
vector<int> tails; // tails[k] = индекс элемента-хвоста длины k+1
vector<int> parent(n, -1);
int best_len = 0, best_idx = -1;
for (int i = 0; i < n; i++) {
// ищем по значениям, но храним индексы
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[tails[mid]] < a[i]) lo = mid + 1; else hi = mid;
}
if (lo > 0) parent[i] = tails[lo - 1];
if (lo == (int)tails.size()) tails.push_back(i);
else tails[lo] = i;
if (lo + 1 > best_len) { best_len = lo + 1; best_idx = i; }
}
vector<int> lis;
for (int i = best_idx; i != -1; i = parent[i]) lis.push_back(a[i]);
reverse(lis.begin(), lis.end());
Сложность O(n log n) по времени, O(n) по памяти. Ключевой момент — tails хранит индексы, а не значения, иначе parent не восстановить. best_idx берётся в момент удлинения хвоста, чтобы не зависеть от перетёртых позже значений.
Частая грабля: для строго возрастающей LIS нужен lower_bound (условие a[tails[mid]] < a[i]), а для неубывающей (где равные элементы можно брать подряд) — upper_bound (a[tails[mid]] <= a[i]). Если перепутать, на тестах с повторами получишь WA: либо потеряешь равные элементы, либо наоборот насчитаешь лишнее. Сначала чётко определись по условию, строгая возрастающая нужна или нет.