题目描述

难度分:$1600$

输入$n$，$m(1 \leq n \times m \leq 10^5)$和$n$行$m$列的矩阵$a$，元素范围$[1,10^9]$。

然后输入$k(1 \leq k \leq 10^5)$和$k$个询问，每个询问输入两个数$L$，$R(1 \leq L \leq R \leq n)$。

对于每个询问，请判断在第$L$行到第$R$行中，是否存在一列，元素值从上到下是递增的（允许相等），输出Yes或No。

输入样例

5 4
1 2 3 5
3 1 3 2
4 5 2 3
5 5 3 2
4 4 3 4
6
1 1
2 5
4 5
3 5
1 3
1 5

输出样例

Yes
No
Yes
Yes
Yes
No

算法

动态规划

状态定义

$up[i][j]$表示在第$j$列中，从第$l$行到第$i$行都能保持单调不减的最小$l$。

状态转移

分为两种情况来讨论

1. 如果$a[i][j] \lt a[i-1][j]$，状态转移方程为$up[i][j]=i$，表示只有第$i$行到第$i$行满足单调不减。
2. 否则状态转移方程为$up[i][j]=up[i-1][j]$，把前一行的答案延续过来。

在读入数据遍历$j$的时候，可以维护$minL[i]=min_{j \in [1,m]}up[i][j]$。随后在面对询问$[L,R]$时，只要$minL[R] \leq L$，就说明存在一列使得从第$L$行到第$R$行单调不减。

复杂度分析

时间复杂度

动态规划在读入数据的时候就可以顺便做完，时间复杂度为$O(nm)$。后续的$k$个查询，每个查询的时间复杂度都是$O(1)$，所以查询的时间复杂度为$O(k)$。因此，算法整体的时间复杂度为$O(nm+k)$。

空间复杂度

空间消耗的瓶颈主要在于DP数组$up$，规模是$nm$的，因此额外空间复杂度为$O(nm)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> minL(n + 1);
    vector<vector<int>> mat(n + 1, vector<int>(m + 1)), up(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++) {
        minL[i] = i;
        for(int j = 1; j <= m; j++) {
            cin >> mat[i][j];
            if(i == 1 || mat[i][j] < mat[i - 1][j]) {
                up[i][j] = i;
            }else {
                up[i][j] = up[i - 1][j];
            }
            minL[i] = min(minL[i], up[i][j]);
        }
    }
    int k;
    cin >> k;
    for(int i = 1; i <= k; i++) {
        int l, r;
        cin >> l >> r;
        if(minL[r] <= l) {
            cout << "Yes" << endl;
        }else {
            cout << "No" << endl;
        }
    }
    return 0;
}