d800: ST版 区间MAX
Tags : RMQ ST segment tree
Accepted rate : 50人/57人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-10-04 10:42

Content

給一個矩陣T(1,1),T(1,2),....T(N,M)  

求T(x1,y1) 到T(x2,y2)的最大值

矩形中的最大元素

Input

每組測資輸入的第一行有兩個整數N,M (1≦N,M≦500) ,

接下來會有N行,每行上會有M個代表T(N,M) (0≦T(N,M) ≦2147483647)

再接下來會有一個整數Q(1≦Q≦1000000),

代表接下來會有Q行詢問的x1,y1,x2,y2(1≦x1≦x2≦N,1≦y1≦y2≦M)。

Output
輸出T(x1,y1) 到T(x2,y2)的最大值
Sample Input
5 6
7 4 3 7 5 1
3 4 7 1 1 6
0 1 8 3 2 5
1 5 9 5 1 5
8 2 6 6 4 5
10
2 4 5 5
1 4 5 5
1 2 3 5
4 2 5 3
4 4 5 5
2 1 5 4
3 4 5 5
2 2 4 2
2 2 2 5
4 3 4 4
Sample Output
6
7
8
9
6
9
6
5
7
9
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 4.0s , <50M
Hint :

AC 得了 d798 的程序不一定 AC 得了 d800;

AC 得了 d800 的程序不一定 AC 得了 d798。

也就是说d798和d800不是简单的重复!

Tags:
RMQ ST segment tree
出處:
d798的另一种版本 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」