Codeforces 777C：Alyona and Spreadsheet（思维）

http://codeforces.com/problemset/problem/777/C

题意：给一个矩阵，对于每一列定义一个子序列使得mp[i][j] >= mp[i-1][j]，即如果满足这样的情况，那么序列长度+1。给出q个询问，问[l,r]的行区间内是否有一个这样的子序列。

思路：用两个数组，第一个数组row记录每一列到第i行的序列长度，第二个数组ans记录每一行到第j列最长的序列长度。然后询问的时候判断ans[r]是否有区间长度大就可以了。

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

1 : row[0] = 1, row[1] = 1, row[2] = 1, row[3] = 1. ans[1] = 1.
2 : row[0] = 2, row[1] = 1, row[2] = 2, row[3] = 1. ans[2] = 2.
3 : row[0] = 3, row[1] = 2, row[2] = 1, row[3] = 2. ans[3] = 3.
以此类推

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 100100
 4 typedef long long LL;
 5 const int INF = 0x3f3f3f3f;
 6 vector<int> mp[N];
 7 int ans[N], row[N];
 8 // row维护的是每一列向上延伸能达到的长度
 9 // ans维护的是当前这一行向上延伸能够达到的最大序列长度,由row取最优得到
10 // 如果ans[r] >= r - l + 1,说明这个区间长度是大于等于[l,r]的
11 
12 int main() {
13     int n, m;
14     scanf("%d%d", &n, &m);
15     for(int i = 0; i < n; i++) {
16         for(int j = 0; j < m; j++) {
17             row[j] = 1;
18             int a; scanf("%d", &a);
19             mp[i].push_back(a);
20         }
21     }
22     ans[1] = 1;
23     for(int i = 1; i < n; i++) {
24         int ma = 0;
25         for(int j = 0; j < m; j++) {
26             if(mp[i][j] >= mp[i-1][j]) row[j]++;
27             else row[j] = 1;
28             if(ma < row[j]) ma = row[j];
29         }
30         ans[i+1] = ma;
31     }
32     int q;
33     scanf("%d", &q);
34     while(q--) {
35         int l, r;
36         scanf("%d%d", &l, &r);
37         if(ans[r] >= r - l + 1) puts("Yes");
38         else puts("No");
39     }
40     return 0;
41 }