Проверьте, есть ли в каком-либо столбце возрастающие элементы в заданном диапазоне для запросов Q.

Опубликовано: 27 Февраля, 2023

Дана матрица mat[][] размера N * M, и Q запрашивает каждый тип {L, R}, который обозначает диапазон строк [L, R]. Задача состоит в том, чтобы проверить, существует ли хотя бы один столбец, элементы которого расположены в порядке возрастания в заданном диапазоне строк (т. е. является ли mat[L][j] ≤ mat[L+1][j] ≤ . . . ≤ mat[R][j] для любого j ).

Примечание. Здесь используется индексация на основе 1.

Пример:

Input: mat[][] = {{1, 2, 3, 5}, {3, 1, 3, 2}, {4, 5, 2, 3}, {5, 5, 3, 2}, {4, 4, 3, 4}}
Q = 6, queries[][] = {{1, 1}, {2, 5}, {3, 5}, {4, 5}, {1, 3}, {1, 5}}
Output: 
YES
NO 
YES
YES
YES 
NO
Explanation: For the first query 1 element is always sorted.
For the second query, there is no column that is sorted.
For the 3rd query elements in 3rd columns are sorted.
For the 4th query elements in 3rd or 4th columns are sorted.
For the 5th query elements in first column are sorted.
For the 6th query there is no such columns which is sorted.

 Input: mat[][] = { {1, 2, 3, 4}, {2, 3, 4, 5}, {3, 4, 5, 6}, {4, 5, 6, 7 }}
Q = 5, queries[][] = { {1, 2}, {2, 3}, {3, 4}, {5, 6}, {7, 8}}
Output: 
YES
YES
YES
NO
NO 

Подход: Задача может быть решена с помощью предварительного вычисления, основанного на следующей идее:

For each column, precalculate the maximum length of the maximum increasing subarray from 1st to ith row. Now while answering each query use the precomputed result to check if the elements in that range are increasing or not.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте матрицу (скажем, dp[][] ), чтобы сохранить результат предварительного вычисления.
  • Для предварительного вычисления вычислите максимальную длину максимального возрастающего подмассива, содержащего элементы столбца, до строки i .
    • Перейдите в каждом столбце от j = 1 до M :
      • Если элемент в i- й строке по крайней мере такой же, как (i-1 ) увеличение строки, то dp[i][j] = dp[i-1][j] + 1 .
      • В противном случае dp[i][j] = 1 .
  • Инициализируйте массив (скажем, ans[] ) для хранения максимальной длины возрастающего подмассива, заканчивающегося i- й строкой среди всех столбцов.
  • Итерация по запросам:
    • Если значение ans[r] для любого запроса не меньше длины диапазона, то существует столбец, удовлетворяющий заданным условиям.
    • В противном случае такой колонки нет.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N*M + Q*M)
Вспомогательное пространство: O(N*M + N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ