cf777c

题意：给你一个n*m的数阵 对于一行到另一行，若存在一列从上到下递减，则称之符合题意
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).
以上是数据范围

a【】来存储每一行的数
b【】来存储每一列能到达的最上行
在用c【】来存储每一行能到达的最上行

#include<cstdio>
using namespace std;
int a[100005],b[100005],c[100005];
int main()
{
    int n,m,x,i,j,r,l,k;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        b[i]=1;
    for(i=1;i<=n;i++){
        c[i]=i;   
        for(j=1;j<=m;j++){
            scanf("%d",&x);
            if(x<a[j])
                b[j]=i;
            a[j]=x;  
            if(b[j]<c[i]) 
              c[i]=b[j];
        }
    }
    scanf("%d",&k);
    while(k--){
        scanf("%d%d",&r,&l);
        if(c[l]<=r)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

。
思路：由于有多次询问所以先打表，记录每一行所能到达的最上行即可

cf777c

原文：https://www.cnblogs.com/pot-a-to/p/10937035.html