d798. 區域MAX - 高中生程式解題系統

內容

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

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

矩形中的最大元素

輸入說明

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

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

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

代表接下來會有 Q 行詢問的 x1 , y1 , x2 , y2

( 1 ≦ x1 ≦ x2 ≦ N , 1 ≦ y1 ≦ y2 ≦ M )。

輸出說明

輸出 T_(x1,y1) 到 T_(x2,y2)的最大值

範例輸入 #1

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

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (95%): 1.0s , <1M
公開測資點#1 (2%): 1.0s , <10M
公開測資點#2 (1%): 1.0s , <10M
公開測資點#3 (1%): 1.0s , <10M
公開測資點#4 (1%): 1.0s , <10M

提示：

Range Minimum/Maximum Query(RMQ)

樹套樹 or 四分樹

標籤:

2D RMQ

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
24872	fire5386 (becaidorz)	d798	2D線段樹	678	2021-04-02 18:36