CodeForces - 777CAlyona and Spreadsheet

题意：

中文

思路：

vector存图，先求每列每个位置开始的最长非降序列的终点。

由于题意只要求满足一列。故不同列中同一起点的最长非降序列记录在一起就可以。

由于我们统计的是终点，故从前向后，后边位置开始的终点必定大于前边位置开始的终点。

最后遍历一边，得到的是从某个位置开始最长非降序列的终点。

代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5+100; int en[MAXN]; vector <int> buf[MAXN]; void get_en(int n,int m){ for(int i=0;i<n;i++) en[i]=i; for(int i=0;i<m;i++){ int st=0; int temp=buf[i][st]; for(int j=0;j<n;j++){ if(buf[i][j]>=temp) en[st]=max(j,en[st]); else st=j; temp=buf[i][j]; } } for(int i=1;i<n;i++) en[i]=max(en[i],en[i-1]); } int main() { ios::sync_with_stdio(false); int n,m,k; while(cin>>n>>m){ for(int i=0;i<m;i++) buf[i].clear(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>k; buf[j].push_back(k); } } get_en(n,m); cin>>k; while(k--){ cin>>n>>m; if(en[n-1]>=m-1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } }

qzh是一个OI的菜鸟，有一天，神犇谢老板给了他一道题。

有一个n*m的矩阵，谢老板会给出若干的询问区间[l,r]（注意是闭区间），qzh需要回答在1到m这些列中有没有一列满足从第l个数到第r个数是从小到大排序的。

但是qzh真是太菜了，不会回答这个问题，请你帮助他回答

Input

输入的第一行包含两个正整数 n 和 m (1 ≤ n·m ≤ 100 000) 分别表示矩阵的行和列。 注意数据保证的是两个数的乘积。

接下来的 n 行每行包括 m 个数. 第 i行中第j个数为a_i, j (1 ≤ a_i, j ≤ 10⁹).

接下来的一行包含一个整数 k (1 ≤ k ≤ 100 000) 表示谢老板给qzh的询问个数

第i个询问包含两个整数l_i 和 r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

对于每一个询问，如果存在一列使得满足谢老板的要求，输出“Yes”（不含引号，下同），否则输出“No”

Example

Input 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 Output Yes No Yes Yes Yes No