Senior 4 — Stalactites
It is now Griffy's turn to hide! Unfortunately, he has strayed a bit too far and has found himself trapped in an ice cave (what are the odds?). Griffy was getting very lonely, so he decided to make friends with all the stalactites in there! The cave is by coincidence a perfect cube . The cube can be thought of as a series of coordinates, where the coordinates are in the range to . At each set of integer coordinates, one stalactite can be found. As an icebreaker, Griffy decides to count the sum of the lengths of all the stalactites inside a rectangular volume. The game gets harder though, as each stalactite can change in length. Given the changing conditions, help Griffy master this game. You can assume that no stalactite changes length while Griffy is counting the sum. Stalactites all start with the same length of . You can also assume that the length of a stalactite at any point will always be a non-negative integer less than or equal to .
Note: At least 30% of the test cases will have all the change length commands coming before the sum commands.
First line: , the size of the cubic cave.
Second line: , the number of events (changing stalactite length, or sum of prism).
The next Q lines are each in the form of:
The stalactite in the coordinate of has changed to a length of .
Find the sum of the stalactites in the rectangular prism bounded by the corners and .
One line, the sum of all of the sum queries.
2 5 C 1 1 2 5 C 1 2 2 5 C 2 1 2 5 S 1 1 1 2 2 2 S 1 1 2 1 1 2
Explanation for Sample Input
The answer to the first sum query is , and the answer to the second one is .