79. 二維陣列單點修改區間查詢總和

二維陣列單點修改區間查詢總和

• 給你一個二維陣列，你有兩個操作可以做：修改某一位置的值和求一個矩形區域的總和
• 小心TLE

輸入說明:

• 輸入的第一行會有兩個正整數$n,m$($1 \leq n,m \leq 1000$)，表示給定的陣列$S$是$n \times m$大小
• 陣列索引值編號從1開始
• 接著會有$n$行，每行有$m$個int範圍的整數，第$i$行第$j$個整數代表陣列$S[i][j]$的值
• 接著有一個整數$t$($0<t \leq 100000$)，表示接下來有$t$個指令要執行
• 指令有兩種:
  • 1 x y c：將$S[x][y]$的值變為c，c為int範圍，$1 \leq x \leq n$，$1 \leq y \leq m$
  • 2 x1 y1 x2 y2：查詢$S$中左上角座標是(x1,y1)，右下角做標是(x2,y2)的子矩形其元素總和，$1 \leq x1 \leq x2 \leq n$，$1 \leq y1 \leq y2 \leq m$

輸出說明

• 對於每個2開頭的指令，請輸出查詢的結果，記得換行

範例輸入:

3 4
1 2 3 4
5 6 7 8
9 10 11 12
14
2 1 1 3 4
2 1 1 2 2
1 1 1 2
1 2 1 3
1 2 2 4
2 1 1 2 2
2 1 1 1 1
2 1 2 1 2
2 2 1 2 1
2 2 2 2 2
1 1 1 5
1 1 1 6
1 1 1 10
2 1 1 1 1

範例輸出:

78
14
11
2
2
3
4
10

配分:

配分	限制
20%	$1 \leq n,m \leq 10$
20%	$1 \leq n,m \leq 100$
60%	沒有限制
時限	500ms
記憶體	31447232 kb

Judge Setting

run-time limit: 500 ms
memory limit: 31447232 byte
測資數量: 0