Условие задачи
Нам дана полностью монотонная матрица размера .
Для каждой строки нужно найти столбец, в котором достигается минимальное значение. Более формально, мы хотим вычислить , где
Нам дана полностью монотонная матрица размера .
Для каждой строки нужно найти столбец, в котором достигается минимальное значение. Более формально, мы хотим вычислить , где
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Ключевое наблюдение состоит в том, что последовательность позиций минимумов по строкам неубывает.
Из-за этого уже можно применить divide and conquer и решить задачу за . Однако существует ещё более быстрый алгоритм под названием SMAWK, который решает её за время .
Алгоритм основан на двух основных идеях: Reduce и Interpolate.
На этом шаге мы пытаемся удалить столбцы, которые точно не могут содержать минимум строки.
Цель — уменьшить число столбцов до не более чем .
Мы поддерживаем стек S столбцов, которые ещё не были исключены. Изначально стек пуст.
Затем мы обрабатываем столбцы слева направо, по одному.
Когда мы обрабатываем столбец j, мы делаем следующее:
S пуст, добавляем столбец j.i = |S|h = S.back()Теперь сравним значения в строке i:
то столбец h можно удалить, поэтому мы выталкиваем его из стека и повторяем.
j добавляется в стек, если размер стека всё ещё меньше N.Так что код выглядит так:
Этот шаг удаляет многие ненужные столбцы, сохраняя при этом все возможные минимумы строк.
Теперь мы решаем задачу рекурсивно только для каждой второй строки, например для всех строк с чётными индексами.
После того как мы узнаем минимумы для этих строк, мы можем восстановить минимумы для оставшихся строк.
Причина в том, что ответ неубывает, поэтому для нечётной строки i мы знаем, что:
Следовательно, чтобы найти f_i, достаточно выполнить линейный поиск только в ограниченном диапазоне от f_{i-1} до f_{i+1}.
Это делает шаг интерполяции эффективным.
Полный алгоритм SMAWK работает следующим образом:
Эти шаги рекурсивно вызывают друг друга, и суммарная сложность равна:
vector<int> S;
for (int j = 1; j <= m; j++) {
while (!S.empty() && a[S.size()][S.back()] > a[S.size()][j]) {
S.pop_back();
}
if ((int)S.size() < n) {
S.push_back(j);
}
}