P4514 Seven Minutes of God Making a Problem

Being naked means having a body.

“Minute 1: X said, let there be a matrix, and so there was an $n\times m$ matrix filled with $0$. Minute 2: L said, let it support modifications, and so there was an operation that adds a value to all numbers in a rectangular region whose top-left corner is $(a,b)$ and bottom-right corner is $(c,d)$. Minute 3: k said, let it support queries, and so there was an operation that computes the sum of all numbers in a given rectangular region. Minute 4: Rainbow Meow said, it should be based on a data structure related to binary trees, and so there were the Constraints. Minute 5: Hexue said, be patient, and so there was a time limit. Minute 6: The piano-eating guy said, save some trouble, and so there was a restriction that during the operations and in the final result, everything will not exceed the range of a 32-bit signed integer type. Minute 7: This problem was finally completed. However, the godlike problem setters no longer wanted to write the program for it.”. — “Seven Minutes of God Making a Naked Problem”. So this sacred task is handed over to you.

The first line of the input is `X n m`, indicating that the matrix size is $n\times m$. From the second line to the end of the file, each line contains one of the following two operations: - `L a b c d delta` — add $delta$ to all numbers in the rectangular region with vertices $(a,b)$ and $(c,d)$. - `k a b c d` — compute the sum of all numbers in the rectangular region with vertices $(a,b)$ and $(c,d)$. Note that $k$ is lowercase.

For each `k` operation, output the answer on a separate line.

For $10\%$ of the testdata, $1 \le n \le 16$, $1 \le m \le 16$, and there are no more than $200$ operations. For $60\%$ of the testdata, $1 \le n \le 512$, $1 \le m \le 512$. For $100\%$ of the testdata, $1 \le n \le 2048$, $1 \le m \le 2048$, $-500 \le delta \le 500$, and there are no more than $2\times 10^5$ operations. It is guaranteed that the final results do not exceed the range of a 32-bit signed integer type, but it is not guaranteed that intermediate computations stay within this range. Translated by ChatGPT 5