UVa11992 - Fast Matrix Operations

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3143

There is a matrix containing at most 106 elements divided into r rows and c columns. Each element has a location (x, y) where 1 ≤ x ≤ r, 1 ≤ y ≤ c. Initially, all the elements are zero. You need to handle four kinds of operations:

1 x1 y1 x2 y2 v Increment each element (x, y) in submatrix (x1, y1, x2, y2) by v (v >0)

2 x1 y1 x2 y2 v Set each element (x, y) in submatrix (x1, y1, x2, y2) to v

3 x1 y1 x2 y2 Output the summation, min value and max value of submatrix(x1, y1, x2, y2)

In the above descriptions, submatrix (x1, y1, x2, y2) means all the elements (x, y) satisfying x1 ≤x ≤ x2 and y1 ≤ x ≤ y2. It is guaranteed that 1 ≤ x1 ≤ x2 ≤ r, 1 ≤ y1 ≤ y2 ≤ c. After any operation,the sum of all the elements in the matrix does not exceed 10^9

Input

There are several test cases. The first line of each case contains three positive integers r, c, m, where m (1 ≤ m ≤ 20, 000) is the number of operations. Each of the next m lines contains a query. There will be at most twenty rows in the matrix. The input is terminated by end-of-file (EOF).

Output

For each type-3 query, print the summation, min and max.

Sample Input

4 4 8

1 1 2 4 4 5

3 2 1 4 4

1 1 1 3 4 2

3 1 2 4 4

3 1 1 3 4

2 2 1 4 4 2

3 1 2 4 4

1 1 1 4 3 3

Sample Output

45 0 5

78 5 7

69 2 7

39 2 7

解題策略：segment tree

將二維陣列轉換成一維陣列，使用區間方式更改segment tree

參考程式碼