P6109 [Ynoi2009] rprmq1

Uh... This problem has an input size of about 13 MB and an output size of about 7 MB. Please choose an appropriate input/output method.

There is an $n \times n$ matrix $a$, initially all $0$. There are $m$ update operations and $q$ query operations. All update operations are performed first, and then all query operations are performed. An update operation gives $l_1,l_2,r_1,r_2,x$, meaning to add a value $x$ to all elements $a_{i,j}$ satisfying $l_1 \le i \le r_1$ and $l_2 \le j \le r_2$. A query operation gives $l_1,l_2,r_1,r_2$, meaning to query the maximum value among all elements $a_{i,j}$ satisfying $l_1 \le i \le r_1$ and $l_2 \le j \le r_2$.

The first line contains three integers $n,m,q$ separated by spaces. The next $m$ lines each contain five integers $l_1,l_2,r_1,r_2,x$, describing an update operation. The next $q$ lines each contain four integers $l_1,l_2,r_1,r_2$, describing a query operation.

Output $q$ lines. For each query operation, output one number per line as the answer.

Idea: apiadu, Solution: ccz181078, Code: apiadu, Data: apiadu & nzhtl1477. Note: This problem uses **bundled subtasks**. You can only get the score for a subtask after passing all test points in that subtask. For $1\%$ of the testdata, it is Sample 1. For another $9\%$ of the testdata, $n=1$. For another $19\%$ of the testdata, $n,m\leq 500$. For another $19\%$ of the testdata, $n\leq 2000$ and $q\leq 2\times 10^5$. For another $19\%$ of the testdata, $m,q\leq 2000$. Constraints: For $100\%$ of the testdata, $1\leq n,m\leq 5\times 10^4$, $1\leq q \leq 5\times 10^5$, $1\leq x\leq 2147483647$, $1\leq l_1\leq r_1\leq n$, $1\leq l_2\leq r_2\leq n$. Translated by ChatGPT 5