d796: 區域調查
Tags : BIT ST
Accepted rate : 56人/61人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 18:31

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
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
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
Hint :

2D Segment Tree (樹套樹 or 四分樹)

2D Binary Index Tree

Tags:
BIT ST
出處:
POJ.1195 Mobile phones 改編 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」