题目链接

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

题目大意

给你一个矩阵，多次询问，每次询问 $L$ 和 $R$ ，你需要回答是否存在一列使得L行到R行为不下降序列

题目分析

这题注意到，只要知道 $L$ 行开始，最长不下降序列最长的那列到哪个位置结束就行了，所以可以先预处理找到所有的不下降序列，就可以找到所有的以某行为起始的最长的不下降序列长度，又因为从前面几行延伸过来的其实也是不下降的，所以再求某一行结束位置和前面几行相比的最大值，查询时比较最大结束位置和 $R$ 谁大就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int n, m;

int a[100005];

struct ex {
    int x;
    int y;
};

ex f[100005];
int cnt = 0;

int v[100005];

int t, k;

int l, r;

int geta(int x, int y){
    return a[(x - 1) * m + y];
}

int init(){
    int i, j;
    
    for(i=1;i<=m;i++){
        l = 1;
        for(j=2;j<=n;j++){
            if(geta(j, i) < geta(j - 1, i)){
                cnt++;
                f[cnt].x = l;
                f[cnt].y = j - 1;
                l = j;
            }
        }
        cnt++;
        f[cnt].x = l;
        f[cnt].y = n;
    }
    
    for(i=1;i<=cnt;i++){
        v[f[i].x] = max(v[f[i].x], f[i].y);
    }
    
    for(i=1;i<=n;i++){
        v[i] = max(v[i], v[i - 1]);
    }
    
    return 0;
}

bool query(int x, int y){
    if(v[x] >= y){
        return true;
    }else{
        return false;
    }
}

int main(){
    int i, j;
    
    scanf("%d", &n);
    scanf("%d", &m);
    
    t = n * m;
    
    for(i=1;i<=t;i++){
        scanf("%d", &a[i]);
    }
    
    init();
    
    scanf("%d", &k);
    
    for(i=1;i<=k;i++){
        scanf("%d", &l);
        scanf("%d", &r);
        if(l == r){
            printf("Yes\n");
        }else if(query(l, r)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    
    return 0;
}