二次元 Sparse Table の構築 Step 1 C編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
説明
この章では、二次元配列に対する Sparse Table の構築方法を学びます。
通常の Sparse Table では
T_{i,k} := i から始まる長さ 2^k の区間の演算結果 としていました。これを二次元に拡張し、
T_{i,j,k,l} := (i,j) を左上とする縦 2^k、横 2^l の長方形領域の演算結果 とします。T_{i,j,k,l} の効率的な構築方法は次の問題で学ぶこととして、この問題では T_{i,j,k,l} を用いて任意の長方形領域の演算結果を求める方法を学びます。
1 次元の場合、区間 [l,r) を覆う 2 つの 2 べきの長さの区間は、k = (2^k ≦ (r-l) を満たす最大の k) として [l, l+2^k) と [r-2^k, r) でした。
2 次元では、(r1,c1) を左上、(r2,c2) を右下とする長方形領域の演算結果を求めたいです（閉区間矩形であることに注意してください）。
まず、行方向と列方向のそれぞれで 2 つの 2 べきの長さの区間に分割することを考えます。
行方向については k = (2^k ≦ (r2-r1+1) を満たす最大の k) として、行方向の区間を [r1, r1+2^k) と [r2-2^k+1, r2+1) に分割します。
同様に列方向については l = (2^l ≦ (c2-c1+1) を満たす最大の l) として、列方向の区間を [c1, c1+2^l) と [c2-2^l+1, c2+1) に分割します。
この k, l を用いて、(r1,c1) を左上、(r2,c2) を右下とする長方形領域の演算結果をいくつかの T_{i,j,k,l} を組み合わせて求めることができます。
具体的には、次の 4 つの T_{i,j,k,l} を組み合わせます。
・T_{r1, c1, k, l}
・T_{r1, c2-2^l+1, k, l}
・T_{r2-2^k+1, c1, k, l}
・T_{r2-2^k+1, c2-2^l+1, k, l}
以下の画像は、(0,0) を左上、(5,6) を右下とする長方形領域を 4 つの T_{i,j,k,l} に分割した例です。
問題
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 ≦ 50
・1 ≦ N ≦ 50
・1 ≦ Q ≦ 10^5
・1 ≦ A_{i,j} ≦ 10^9
・0 ≦ r1 ≦ r2 < M
・0 ≦ c1 ≦ c2 < N
- 入力例1
-
4 5 5
3 4 16 2 16
6 17 16 15 5
2 5 3 15 15
2 4 16 8 9
0 2 3 2
1 1 3 2
1 4 1 4
1 2 2 4
0 1 0 4
- 出力例1
-
3
3
5
3
2
- 入力例2
-
4 4 5
4 111111115 222222231 333333342
111111120 222222231 333333335 444444450
222222231 333333339 444444454 555555564
333333341 444444453 555555557 666666675
0 0 3 2
0 1 0 2
0 2 0 2
1 0 2 0
0 1 2 2
- 出力例2
-
4
111111115
222222231
111111120
111111115
- 入力例3
-
9 6 10
851267995 83802322 651439052 434839847 226485026 705363477
381463275 686450563 974842385 571146930 37539110 768772067
238043309 544628185 65291746 874464275 184173629 111814178
486914972 71321976 684929167 50266966 700302644 254915931
985287113 529039158 517896636 874489436 804328894 437633038
707288017 935891090 379614367 625691051 123074456 159045082
945971993 577222772 799476829 233877071 630953195 134824429
350155694 566625516 782753520 795488662 312679570 218839788
389805625 970665459 51520448 140625250 910424910 770251125
5 4 7 4
2 1 8 5
0 1 1 4
1 0 6 5
5 0 7 3
1 2 8 4
3 1 6 3
5 2 8 5
6 1 7 3
3 4 7 4
- 出力例3
-
123074456
50266966
37539110
37539110
233877071
37539110
50266966
51520448
233877071
123074456
