二次元 Sparse Table 練習問題 Bash(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
M 行 N 列のグリッドが与えられます。
グリッドの各マスには整数 A_{i,j} が書かれています。
また、整数 H, W が与えられます。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・r1 c1 r2 c2：(r1,c1) を左上、(r2,c2) を右下とする長方形領域に完全に含まれる H 行 W 列の長方形領域のうち、領域内の総和の最大値を出力する。
答えが 32bit 整数に収まらない可能性があることに注意してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
M N Q H W
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, H, W がこの順に半角スペース区切りで与えられます。
・続く M 行の i 行目には グリッドの i 行目の要素 A_{i,0}, A_{i,1}, ..., A_{i,N-1} が半角スペース区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で M+Q+1 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ H ≦ M ≦ 500
・1 ≦ W ≦ N ≦ 500
・1 ≦ Q ≦ 10^5
・1 ≦ A_{i,j} ≦ 10^9
・0 ≦ r1 ≦ r2 < M
・0 ≦ c1 ≦ c2 < N
・r2 - r1 + 1 ≧ H
・c2 - c1 + 1 ≧ W
- 入力例1
-
4 5 5 2 2
4 6 15 19 17
16 16 5 15 17
14 12 15 1 5
9 8 10 19 12
2 3 3 4
1 0 2 3
2 2 3 3
1 3 3 4
1 0 2 4
- 出力例1
-
37
58
45
38
58
- 入力例2
-
4 4 5 2 2
6 111111119 222222224 333333335
111111113 222222225 333333335 444444448
222222226 333333340 444444452 555555564
333333339 444444448 555555559 666666672
0 2 1 3
1 2 3 3
0 1 1 2
2 1 3 2
2 2 3 3
- 出力例2
-
1333333342
2222222247
888888903
1777777799
2222222247
- 入力例3
-
9 6 10 3 3
334557269 807728937 1060484 215625086 996514680 389768911
345002151 770756580 661659313 299810129 87177692 425045087
611445229 780854357 543116289 559951636 255227484 822997886
770579925 904534478 210993326 198710365 619894493 961753978
374696065 117176248 592306500 32209154 198801104 356608160
179375043 419708530 107518663 797785539 354484098 284919825
369649340 865906228 297632347 814299462 648288535 711531015
106519285 537142776 964838672 812422428 89103098 986678379
910367259 99533461 374379613 649951078 17528787 237126787
6 3 8 5
5 1 7 3
2 2 4 4
5 1 7 5
0 1 7 4
6 2 8 5
0 1 2 3
3 2 5 5
5 3 7 5
6 2 8 4
- 出力例3
-
4966929569
5617254645
3211210351
5617254645
5617254645
4966929569
4640562811
3805166716
5499512379
4668444020
