d796.
區域調查
Content
給一個矩陣 T(1,1), T(1,2),.... T(N,M)
求 T(x1,y1) 到 T(x2,y2) 的總和 或者是修改 T(x1,y1) 的值
矩形中的元素總和
Input
每組輸入的第一行會有兩個正整數 N Q ( 1 ≦ N ≦ 250, Q ≦ 50,0000)
接下來會有 N 行，每行上會有 N 個元素 M ( 0 ≦ M ≦ 32767 )
接下來會有 Q 行，倘若第一個數字為 1，則接下來會有四個數字
x1 , y1 , x2 , y2， 1 ≦ x1 , y1 , x2 , y2 ≦ 250
請輸出元素 S={( x , y ) | x1 ≦ x ≦ x2, y1 ≦ y ≦ y2 }符合的所有元素總和
倘若第一個數字為2，則接下來會有三個數字
x1 , y1 , V， 1 ≦ x1 , y1 ≦ 250 , 0 ≦ V ≦ 32767,
請修改 ( x1 , y1 )= V ; 此行不必輸出
Output
若為調查，則輸出區域中的元素總和，若為修正，則不必輸出
Sample Input
#1
5 10 3 2 2 3 7 4 4 0 3 8 2 4 7 2 3 5 9 6 1 4 7 1 7 1 1 2 2 2 1 1 5 4 5 5 2 2 1 7 1 3 2 1 5 1 2 5 4 5 1 1 2 2 1 2 2 2 7 2 4 5 5 1 3 3 4 5 1 4 3 2 2
Sample Output
#1
2 42 15 13 24 33
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (50%): 2.0s , <10M
公開 測資點#1 (30%): 2.0s , <10M
公開 測資點#2 (10%): 2.0s , <10M
公開 測資點#3 (5%): 2.0s , <10M
公開 測資點#4 (4%): 2.0s , <1M
公開 測資點#5 (1%): 2.0s , <10M
公開 測資點#0 (50%): 2.0s , <10M
公開 測資點#1 (30%): 2.0s , <10M
公開 測資點#2 (10%): 2.0s , <10M
公開 測資點#3 (5%): 2.0s , <10M
公開 測資點#4 (4%): 2.0s , <1M
公開 測資點#5 (1%): 2.0s , <10M
Hint ：
2D Segment Tree (樹套樹 or 四分樹)
2D Binary Index Tree
出處:
POJ.1195 Mobile phones 改編
[管理者：
morris1028(碼畜)
]