題干：

During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.

Now she has a table filled with integers. The table consists of?n?rows and?mcolumns. By?ai,?j?we will denote the integer located at the?i-th row and the?j-th column. We say that the table is sorted in non-decreasing order in the column?j?if?ai,?j?≤?ai?+?1,?j?for all?i?from?1?to?n?-?1.

Teacher gave Alyona?k?tasks. For each of the tasks two integers?l?and?r?are given and Alyona has to answer the following question: if one keeps the rows from?l?to?rinclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such?j?that?ai,?j?≤?ai?+?1,?j?for all?i?from?l?to?r?-?1?inclusive.

Alyona is too small to deal with this task and asks you to help!

Input

The first line of the input contains two positive integers?n?and?m?(1?≤?n·m?≤?100?000)?— the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.

Each of the following?n?lines contains?m?integers. The?j-th integers in the?i?of these lines stands for?ai,?j?(1?≤?ai,?j?≤?109).

The next line of the input contains an integer?k?(1?≤?k?≤?100?000)?— the number of task that teacher gave to Alyona.

The?i-th of the next?k?lines contains two integers?li?and?ri?(1?≤?li?≤?ri?≤?n).

Output

Print "Yes" to the?i-th line of the output if the table consisting of rows from?lito?ri?inclusive is sorted in non-decreasing order in at least one column. Otherwise, print "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

Note

In the sample, the whole table is not sorted in any column. However, rows 1–3 are sorted in column?1, while rows 4–5 are sorted in column?3.

題目大意：

給出n*m的矩陣，有k次查詢，每次查詢給出l和r，如果第l行到r行至少有一列是非遞減的，則輸出Yes，否則輸出No

解題報告：

預處理一個數組sum，按列更新，考慮sum[i][j]，如果這個數比他上面那個數大的話，就sum[i-1][j]+1，否則為1.

然后看到給出的詢問都是對于行的，所以我們先把對于每一行而言，每一列的信息都壓縮給這一行，維護一個c數組，對于每一行，二分查找他能遞增到的最大的行，對于check函數，只要判斷區(qū)間和是否等于區(qū)間長度即可，注意取前綴和的時候不能sum[r]-sum[l-1]了，因為這個前綴信息是斷裂的，所以需要sum[r]-sum[l]+1這樣。每次查詢的時候O1輸出即可。總復雜度O(n*m*log(n))

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m,c[MAX]; vector<vector<int>> vv,sum; bool ok(int up,int down) {for(int j = 1; j<=m; j++) {if(sum[down][j] - sum[up][j] +1 == down-up+1) return 1;}return 0; } int main() {cin>>n>>m;vv.resize(n+1);sum.resize(n+1);for(int i = 0; i<=n; i++) {vv[i].resize(m+1);sum[i].resize(m+1);}for(int x,i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) scanf("%d",&x),vv[i][j]=x;}for(int j = 1; j<=m; j++) {for(int i = 1; i<=n; i++) {if(vv[i][j] >= vv[i-1][j]) sum[i][j] = sum[i-1][j]+1;else sum[i][j] = 1;}}for(int i = 1; i<=n; i++) {int l=i,r=n,mid,ans=0;while(l<=r) {mid=(l+r)>>1;if(ok(i,mid)) l = mid+1,ans = mid;else r = mid-1;}c[i] = ans;}int q,l,r;cin>>q;while(q--) {scanf("%d%d",&l,&r);if(c[l] >= r) puts("Yes");else puts("No"); }return 0 ; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 777C】Alyona and Spreadsheet（思维，前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。