二次元 Sparse Table の構築 Step 2 Clojure(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
説明
T_{i,j,k,l} := (i,j) を左上とする縦 2^k、横 2^l の長方形領域の演算結果 の効率的な計算方法を説明します。1 次元の場合、T_{i,k} は次のように構築しました。
1. T_{i,0} = A_i
2. T_{i,k} = T_{i,k-1} と T_{i+2^{k-1},k-1} を組み合わせたもの（k ≧ 1）
2 次元の場合では、行方向および列方向にわけて同様の方法で構築します。
1. T_{i,j,0,0} = A_{i,j}
2. T_{i,j,0,l} = T_{i,j,0,l-1} と T_{i,j+2^{l-1},0,l-1} を組み合わせたもの（l ≧ 1）
・横方向に構築（高さ 1 で固定して横幅を広げていく）
・言い換えると、行 i における 1 次元 Sparse Table の構築
3. T_{i,j,k,l} = T_{i,j,k-1,l} と T_{i+2^{k-1},j,k-1,l} を組み合わせたもの（k ≧ 1）
・2. で構築した T_{i,j,0,l} を利用して縦方向に構築
・任意の横幅 2^l に対して、縦方向に高さを広げていく
最後に計算量について説明します。
M 行 N 列の二次元配列に対して、T_{i,j,k,l} の添え字は
・0 ≦ i < M
・0 ≦ j < N
・0 ≦ k ≦ log_2(M)
・0 ≦ l ≦ log_2(N)
となります。
したがって、T_{i,j,k,l} の要素数は O(MN logM logN) です。
各要素の計算は定数時間でおこなえるため、全体の構築にかかる時間は O(MN logM logN) となります。
問題
M 行 N 列のグリッドが与えられます。
グリッドの各マスには整数 A_{i,j} が書かれています。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・
r1 c1 r2 c2：(r1,c1) を左上、(r2,c2) を右下とする長方形領域の最小値 min(A_{r1,c1}, A_{r1,c1+1}, ..., A_{r1,c2}, A_{r1+1,c1}, A_{r1+1,c1+1}, ..., A_{r1+1,c2}, ..., A_{r2,c1}, A_{r2,c1+1}, ..., A_{r2,c2}) を出力する。（クエリが閉区間矩形で与えられることに注意してください）
- 入力される値
-
入力は以下のフォーマットで与えられます。
M N Q
A_{0,0} A_{0,1} ... A_{0,N-1}
A_{1,0} A_{1,1} ... A_{1,N-1}
...
A_{M-1,0} A_{M-1,1} ... A_{M-1,N-1}
r1_1 c1_1 r2_1 c2_1
r1_2 c1_2 r2_2 c2_2
...
r1_Q c1_Q r2_Q c2_Q
・1 行目には整数 M, N, Q がこの順に半角スペース区切りで与えられます。
・続く M 行の i 行目には グリッドの i 行目の要素 A_{i,0}, A_{i,1}, ..., A_{i,N-1} が半角スペース区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で M+Q+1 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ M ≦ 500
・1 ≦ N ≦ 500
・1 ≦ Q ≦ 10^5
・1 ≦ A_{i,j} ≦ 10^9
・0 ≦ r1 ≦ r2 < M
・0 ≦ c1 ≦ c2 < N
- 入力例1
-
4 5 5
1 11 10 20 10
4 12 2 9 12
4 4 4 17 19
18 5 17 14 6
0 1 2 1
0 0 3 4
0 3 0 4
0 3 0 3
2 1 3 2
- 出力例1
-
4
1
10
20
4
- 入力例2
-
4 4 5
3 111111121 222222232 333333338
111111118 222222229 333333334 444444454
222222227 333333338 444444448 555555563
333333337 444444446 555555556 666666671
1 1 3 1
0 1 3 3
3 2 3 3
1 0 2 0
1 0 3 3
- 出力例2
-
222222229
111111121
555555556
111111118
111111118
- 入力例3
-
9 6 10
600145912 684935765 647678299 818556625 218812060 22502680
636151920 667343218 821582155 929989267 544989250 490101825
72699658 928288358 106148348 897486398 637805573 640029476
362308466 576506509 628647600 246930147 668931506 432159370
580685672 826409275 110652215 147419333 277312852 262665867
57345751 736100715 248482788 77511339 324102316 323984301
501107378 7972238 939084254 283104562 951922136 233396030
857913883 101185275 436931392 892399578 669208474 244861394
197822105 4649708 18984982 38976859 278239588 585987984
6 1 6 2
2 2 2 4
4 4 6 5
1 1 2 2
2 0 2 5
3 2 3 5
1 2 6 2
6 1 7 1
0 1 8 2
7 1 8 5
- 出力例3
-
7972238
106148348
233396030
106148348
72699658
246930147
106148348
7972238
4649708
4649708
