CF555C Case of Chocolate

Andrewid the Android 是一名闻名银河系的侦探。现在他没有在侦破案件，而是百无聊赖地吃巧克力。 一块巧克力可以被表示为一个 $n \times n$ 的方格，每个格子代表一块巧克力。表格的列从左到右编号为 $1$ 到 $n$，行从上到下编号为 $1$ 到 $n$。我们称从左下角到右上角的对角线为反对角线。首先，Andrewid 会吃掉所有位于反对角线下方的巧克力块。随后，对于剩下的三角形部分，他会进行 $q$ 次操作：每次操作会选择反对角线上的某一块巧克力，以及一个方向（“上”或“左”），然后从所选单元格出发，按照指定方向连续吃掉所有巧克力，直到遇到已经被吃掉的格子或者巧克力的边界为止。 每次操作之后，他都想知道此次操作中他吃掉了多少块巧克力。

第一行包含两个整数 $n$（$1 \leq n \leq 10^{9}$）和 $q$（$1 \leq q \leq 2 \cdot 10^{5}$），表示巧克力的边长以及操作次数。 接下来 $q$ 行，每行描述一次操作，第 $i$ 行包含数字 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$，且 $x_i + y_i = n + 1$），表示选中的巧克力块所在的列和行的编号，以及一个字符，表示方向（L 表示向左，U 表示向上）。

输出 $q$ 行，第 $i$ 行表示第 $i$ 次操作中 Andrewid 吃掉的巧克力块数。

样例测试的图片如下：  同一次操作吃掉的巧克力块用同一种颜色标记。位于反对角线上的格子内写有此次操作的编号，表示这些格子是在第几次操作中被吃掉的。 在第二组样例中，Andrewid 在第五次操作时，又尝试从第 10 列第 1 行开始吃巧克力，但这个格子已经被吃掉了，因此这次操作他没有吃到任何巧克力。 由 ChatGPT 5 翻译