P5897 [IOI 2013] wombats

Brisbane has been occupied by mutated wombats, and you must lead everyone to a safe place. The roads in Brisbane form a large grid. There are $R$ horizontal roads running west to east, numbered from north to south as $0,\cdots,(R - 1)$. There are $C$ vertical roads running south to north, numbered from west to east as $0,\cdots,(C - 1)$, as shown in the figure below.  Wombats invade from the north, and people escape to the south. People can move in both directions along horizontal roads, but along vertical roads they can only move south toward safety. The intersection of horizontal road $P$ and vertical road $Q$ is denoted as $(P, Q)$. On each road segment between two adjacent intersections, there are some wombats, and the number changes over time. Your task is to guide each person from a specified intersection on the northernmost road (horizontal road $0$) to a specified intersection on the southernmost road (horizontal road $R - 1$), while encountering as few wombats as possible along the way. You are first given the grid size and the number of wombats on each road segment. Then you are given a sequence of $E$ events, each of which is one of the following: - an update, meaning the number of wombats on some road segments changes; - an escape query, meaning some people have arrived at a specified intersection on horizontal road $0$, and you must tell them a path to a specified intersection on horizontal road $R - 1$ that minimizes the number of wombats encountered. **Example**  In the initial map shown above, there are $3$ horizontal roads ($R = 3$) and $4$ vertical roads ($C = 4$). The number of wombats on each road segment is marked on the segment. Consider the following events: - A person arrives at intersection $A = (0, 2)$ and wants to escape to intersection $B = (2, 1)$. As shown by the dashed path, they need to pass at least $2$ wombats. - Another person arrives at intersection $X = (0, 3)$ and wants to escape to intersection $Y = (2, 3)$. As shown by the dashed path, they need to pass at least $7$ wombats. - Two update events occur: the number of wombats on the topmost vertical segment of vertical road $0$ becomes $5$, and the number of wombats on the middle horizontal segment of horizontal road $1$ becomes $6$, as circled in the figure below.  - A third person arrives at intersection $A = (0, 2)$ and wants to escape to intersection $B = (2, 1)$. Now they need to pass at least $5$ wombats, as shown by the dashed path in the figure.

- Line $1$: $R$ is the number of horizontal roads, and $C$ is the number of vertical roads. - Line $2$: $H[0][0],\cdots,H[0][C-2]$. - $\cdots$ - Line $(R + 1)$: $H[R-1][0],\cdots,H[R-1][C-2]$. - Line $(R + 2)$: $V[0][0],\cdots,V[0][C-1]$. - $H$: a 2D array of size $R \times (C - 1)$, where $H[P][Q]$ is the number of wombats on the horizontal road segment between intersection $(P, Q)$ and intersection $(P, Q + 1)$. - $\cdots$ - Line $(2R)$: $V[R-2][0],\cdots,V[R-2][C-1]$. - $V$: a 2D array of size $(R - 1) \times C$, where $V[P][Q]$ is the number of wombats on the vertical road segment between intersection $(P, Q)$ and intersection $(P + 1, Q)$. - Next line: $E$. - The next $E$ lines: one event per line, given in the order they occur. If $C = 1$, then the empty lines for the number of wombats on horizontal road segments (lines $2$ to $R + 1$) will be omitted. The format of each event line is as follows: - `1 P Q W` means setting the number of wombats on the horizontal road segment between intersection $(P, Q)$ and intersection $(P, Q + 1)$ to $W$. - `2 P Q W` means setting the number of wombats on the vertical road segment between intersection $(P, Q)$ and intersection $(P + 1, Q)$ to $W$. - `3 V1 V2` means computing the minimum number of wombats a person must pass when escaping from intersection $(0, V1)$ to intersection $(R-1, V2)$. For example, the example in the statement should be written in the following format: ``` 3 4 0 2 5 7 1 1 0 4 0 0 0 0 2 0 3 4 7 5 3 2 1 3 3 3 2 0 0 5 1 1 1 6 3 2 1 ```

For each query, output the minimum number of wombats that must be passed.

Constraints: for $100\%$ of the data, $2 \le R \le 5 \times 10^3$, $1 \le C \le 200$, there are at most $500$ updates, at most $2 \times 10^5$ queries, and at any time there are at most $10^3$ wombats on any road segment. Translated by ChatGPT 5