P4054 [JSOI2009] Counting Problem

There is an $n \times m$ grid. Initially, each cell has an integer weight. Then there are 2 types of operations: - Change the weight of a cell. - Query how many times a specified weight appears in a submatrix.

The first line contains two integers $n, m$. Then follow $n$ lines, each with $m$ integers. In the $(i+1)$-th line, the $j$-th number is the initial weight of cell $(i, j)$. Then an integer $Q$ is given. Then there are $Q$ lines, each describing an operation. Operation 1: A line with four integers $1\ x\ y\ c$, meaning set the weight of cell $(x, y)$ to $c$. Operation 2: A line with six integers $2\ x_1\ x_2\ y_1\ y_2\ c$, meaning query the number of cells whose weight is $c$ and satisfy $x_1\le x\le x_2, y_1\le y\le y_2$.

For each operation 2, output one integer per line in the order they appear, representing the required count.

Constraints For $30\%$ of the testdata: $n, m\le 30$, $Q\le 5\times 10^4$. For $100\%$ of the testdata: $1\le n, m\le 300$, $1\le Q\le 2\times 10^5$. For operation 1, it is guaranteed that $1\le x\le n$, $1\le y\le m$, $1\le c\le 100$. For operation 2, it is guaranteed that $1\le x_1\le x_2\le n$, $1\le y_1\le y_2\le m$, $1\le c\le 100$. Translated by ChatGPT 5