最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 矩阵最值

C++ 少儿编程 1295浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

我们有一个$n$行$m$列的矩阵,现在小Q有$K$个问题,每次询问一个以$x_1$行$y_1$列为左上角,$x_2$行$y_2$列为右下角的子矩阵的最大值。

【输入】

第一行三个整数$n,m,K$。$(n,m≤250,K≤10^6)$

接下去$n$行,每行有$m$个整数,设$a[i][j]$为矩阵$i$行$j$列的数字,保证$0≤a[i][j]<2^{31}$。

接下去$K$行,每行$4$个整数$x_1,y_1,x_2,y_2$,保证$(x_1≤x_2,y_1≤y_2)$。

【输出】

共$K$行,每行对应一个答案。

【输入样例】

3 4 5
789 15225 27847 6452 
3976 18268 23626 1943 
13336 26216 17321 4960 
2 2 3 4
2 3 3 4
2 1 3 4
1 3 2 4
1 2 3 2

【输出样例】

26216
23626
26216
27847
26216

【提示】

【数据规模】

对于30%的数据, $n,m≤50,K≤1000$。

对于50%的数据, $n,m≤250,K≤10000$。

对于100%的数据, $n,m≤250,K≤10^6$。

您必须 登录 才能发表评论!