Вот и первая не комбинаторная ДП.

1. Двуменное $dp[i][j]$ — для столбика $i$ и строки $j$ храним максимальную строку ниже, такую, что все числа вниз по строке от $j$ до $dp[i][j]$ будут отсортированы.
2. Начальное значение $dp[i][j]=j$.
3. Пересчёт $dp[i][j]=dp[i][j-1]+1$, если $a_{i,j-1}\le a_{i,j}$.
4. Ответ? У нас задача о запросах.

Тогда для ответа YES на запрос $[l,r]$ надо чтобы хотя бы для одного $i$ (от $1$ до $m$) $dp[i][l]\ge r$, а это тождественно $max(dp[i][l])\ge r$.

Заведём массив $best[l]=\max (dp[i][l])$ по всем $i$ от $1$ до $m$.

Решение за $o(n\times m)$ на предпосчёт и $o(1)$ на запрос.

TODO код