P5620 [DBOI2019] Coin Picking.

> As everyone knows, Itsumade is the cutest in the world. > ——1jia1 You are playing the non-pay-to-win mobile game yys. At this moment, your parents walk in, so you pretend you are working on a data structure problem. 

After $n$ ten-pulls, you have run out of money, so you accept Itsumade’s invitation to join an event. This event takes place in an $n \times n$ rectangular area and lasts for several seconds. At second $i$, the organizer chooses a small sub-rectangle inside it and drops coins onto each cell in that sub-rectangle. The rules for picking coins are as follows: start from the top-left corner $(1,1)$ and walk along a path that reaches $(n,n)$. Each move can only go to the cell below or to the cell on the right of the current cell, and you pick up the coins in the visited cells. You need to find: at some moment, within a given rectangular area, how many coins are on the cell with the most coins; the total number of coins in a given rectangular area; and after second $m$ (if there is a coin-dropping operation at that time, drop coins first), the maximum number of coins you can pick up. During the picking process, the amount of coins on the board does not change; you may assume this is completed within $1$ second.

The first line contains integers $n, m, Q\ (m\leq\text{number of coin-dropping operations})$. The next $Q$ lines each contain five integers $u, x1, y1, x2, y2$ ($0 < x1 \leq x2 \leq n$, $0 < y1 \leq y2 \leq n$, $-1 \leq u \leq 10$). - If $u > 0$, it is a coin-dropping operation: $u$ coins are added to every cell in the rectangle with top-left and bottom-right corners $(x1,y1)$ and $(x2,y2)$. The time of coin-dropping operations increases in order (that is, the first coin-dropping operation happens at the first second, the second at the second second, ...). - If $u = 0$, it is a max query operation: ask, after the most recent coin-dropping operation, what is the maximum coin value among all cells in the rectangle with corners $(x1,y1)$ and $(x2,y2)$. (See the description for the exact meaning.) - If $u = -1$, it is a sum query operation: ask, after the most recent coin-dropping operation, what is the total sum of coin values of all cells in the rectangle with corners $(x1,y1)$ and $(x2,y2)$.

Output several lines. The first several lines each output one integer, which is the answer to each query. The last line outputs the maximum number of coins you can obtain by picking coins after dropping coins at second $m$.

【Sample #1 Explanation】     ### Constraints and Notes - Subtask #1 ($20$ points): $1 \leq n \leq 10$, $1 \leq Q \leq 1000$. - Subtask #2 ($20$ points): $1 \leq n \leq 1000$, $1 \leq Q \leq 10$. - Subtask #3 ($20$ points): $1 \leq n \leq 100$, $1 \leq Q \leq 1000$. - Subtask #4 ($40$ points): $1 \leq n \leq 1000$, $1 \leq Q \leq 10000$. Translated by ChatGPT 5