P15351 [COCI 2025/2026 #4] Tomahawk Steak / Tomahawk

Consider an $n\times n$ matrix $A$. Initially, all elements in $A$ are zero. Use the following conventions: rows are horizontal and columns are vertical. Rows are numbered from top to bottom as $1\sim n$, and columns are numbered from left to right as $1\sim n$. There are $q$ operations: - $\texttt{L}$ $x$: here, $1\le x\le \lfloor \frac{n+1}{2}\rfloor$. - For $i=1,\ldots,x$, add $(x-i+1)$ to every cell in column $i$. - $\texttt{R}$ $x$: here, $1\le x\le \lfloor \frac{n+1}{2}\rfloor$. - For $i=1,\ldots,x$, add $(x-i+1)$ to every cell in column $(n-i+1)$. - $\texttt{D}$ $x$: here, $1\le x\le n$. - For $i=1,\ldots,x$, add $(x-i+1)$ to every cell in row $(n-i+1)$. After all operations, find the range of the matrix (the difference between the maximum value and the minimum value).

The first line contains two positive integers $n,q$ ($1\le n\le 10^9$, $1\le q\le 10^5$). The next $q$ lines each contain a character $s$ and a positive integer $x$, where $s\in \{\texttt{L},\texttt{R},\texttt{D}\}$. - If $s=\texttt{D}$, then $1\le x\le n$; - otherwise, $1\le x\le \lfloor \frac{n+1}{2}\rfloor$.

Output one integer on a single line, representing the range (the difference between the maximum value and the minimum value).

### Sample Explanation Explanation for sample 1: $\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \end{bmatrix}$ Explanation for sample 2: $\begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \\ 0 & 1 & 2 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \\ 3 & 5 & 7 \end{bmatrix}$ ### Subtasks | Subtask ID | Score | Constraints | | :-: | :-: | :- | | $1$ | $7$ | $n,q\le 20$ | | $2$ | $22$ | $n,q\le 100$ | | $3$ | $31$ | $n\le 1000$ | | $4$ | $6$ | $n$ is even | | $5$ | $4$ | No additional constraints | Translated by ChatGPT 5