-
分析
先对每一列都做 DP 寻找极长单调不降区间，能够得到若干极长单调不降区间，只要询问的区间是这些区间的子区间，那么说明在这个区间内必有一列的这个区间是单调不降的。
思考如何快速判断子区间。
用 \(f_{x}\) 表示以 \(x\) 为所有左端点为 \(x\) 的区间的右端点最大值，那么对于询问区间 \([L,R]\)，我们只需要判 \(R \leq f_{L}\) 就可以证明合法，反之则不合法。思考如何求 \(f_{x}\) 数组。
首先 \(f_{x}\) 一定等于所有左端点为 \(x\) 的极长区间的右端点最大值，同时对于左端点小于 \(x\) 的所有极长区间，其右端点的最大值也可以传递给 \(x\)。
那么我们先求一遍 \(f_x\) 表示所有左端点为 \(x\) 的极长区间的右端点最大值，然后再求一遍前缀最大值表示所有左端点为 \(x\) 的区间的右端点最大值。值得注意的是，因为这个数组的二维可能有一维过大，所以要先用一维数组存储，然后再按下标对 \(m\) 取模的模数分类存到 vector 里就可以当成二维数组做了。
-
代码
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN(1000007);
vector <int> e[MAXN];
int r[MAXN], a[MAXN];
int n, m, q;
inline void read(int &temp) { cin >> temp; }
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n), read(m);
for (int i(1); i <= n * m; ++i) read(a[i]);
for (int j(0); j < m; ++j) e[j].push_back(0);
for (int i(1); i <= n * m; ++i) e[i % m].push_back(a[i]);
for (int j(0); j < m; ++j) {
int lst(1);
for (int i(1); i <= n; ++i) if (e[j][i] < e[j][i - 1]) r[lst] = max(r[lst], i - 1), lst = i;
r[lst] = max(r[lst], (int)e[j].size() - 1);
}
for (int i(1); i <= n; ++i) r[i] = max(i, max(r[i - 1], r[i]));
read(q);
for (int i(1), L, R; i <= q; ++i) {
read(L), read(R);
if (R > r[L]) cout << "No" << endl;
else cout << "Yes" << endl;
}
return 0;
}