1007. 反弹小球

题目描述

在一个 $n \times m$ 的二维整数格点矩形区域内（格点坐标范围为 $1 \le x \le n, 1 \le y \le m$），依次放入 $k$ 个小球。

每个小球 $i$ 的初始状态由初始位置 ($x_i, y_i$) 和初始速度向量 ($v_{x_i}, v_{y_i}$) 定义，其中 $v_{x_i}, v_{y_i} \in \{-1, 1\}$。小球在离散的时间步中运动。在每一个时间步中，小球尝试根据当前速度移动到下一个位置，具体的移动逻辑如下：

1. 碰撞判定：对于每一个维度，独立判断在该维度上是否即将运动到台球桌外。
   • 如果 $1 \le x + v_x \le n$，则水平速度 $v_x$ 保持不变。
   • 如果 $x + v_x < 1$ 或 $x + v_x > n$，则该维度的方向发生改变，即 $v_x \leftarrow -v_x$。
   • 垂直维度 $y$ 同理：如果 $y + v_y < 1$ 或 $y + v_y > m$，则 $v_y \leftarrow -v_y$。
2. 位置更新：在确定了最终的速度方向后，小球移动到新位置 $x + v_x, y + v_y)$。

可以前往样例解释以进一步理解具体的运动逻辑。

不同小球之间相互独立，即使处于同一位置也不会发生碰撞。小球会无限运动下去。对于每个 $i \in \{1, 2, \dots, k\}$，请你求出：在第 $i$ 个小球放下后，在无限时间里，至少被一个小球经过的格点数量总和

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含三个整数 $n, m, k$（$2 \le n, m \le 5 \times 10^5, 1\le k\le 5 \times 10^5$），分别表示网格的宽度、高度和小球的数量。
• 接下来 $k$ 行，第 $i$ 行包含四个整数 $x_i, y_i, v_{x_i}, v_{y_i}$（$1 \le x_i \le n, 1 \le y_i \le m, v_{x_i}, v_{y_i} \in \{-1, 1\}$），表示第 $i$ 个小球的初始位置和速度方向。

数据保证所有测试数据的 $\sum n, \sum m, \sum k$ 均不超过 $5\times 10^6$。

输出格式

对于每组测试数据，输出一行 $k$ 个整数，第 $i$ 个整数表示加入前 $i$ 个小球后，被经过的格点总数。

样例输入

1
3 3 3
2 1 1 1
1 1 1 1
3 1 1 -1

样例输出

4 7 9

提示

在 $3 \times 3$ 的网格中：

1. 第 1 个球从 ($2, 1$) 出发，速度为 ($1, 1$)：
   • $2, 1) \to 3, 2)$ （撞右墙，$v_x$ 变为 $-1$） $\to 2, 3)$ （撞上墙，$v_y$ 变为 $-1$） $\to 1, 2)$ （撞左墙，$v_x$ 变为 $1$） $\to 2, 1)$。
   • 轨迹点集：$\{2,1), 3,2), 2,3), 1,2)\}$，共 4 个点。
2. 第 2 个球从 $1, 1)$ 出发，速度为 $1, 1)$：
   • $1, 1) \to 2, 2) \to 3, 3)$ （双向撞墙，$v_x, v_y$ 均取反） $\to 2, 2) \dots$
   • 轨迹点集：$\{1,1), 2,2), 3,3)\}$。
   • 前两个球的并集为 $\{2,1), 3,2), 2,3), 1,2), 1,1), 2,2), 3,3)\}$，共 7 个点。
3. 第 3 个球从 $3, 1)$ 出发，速度为 $1, -1)$：
   • $3, 1) \to 2, 2) \to 1, 3) \to 2, 2) \dots$
   • 轨迹点集：$\{3,1), 2,2), 1,3)\}$。注意 $2,2)$ 之前已被小球 2 经过。
   • 前三个球的并集包含网格内所有 9 个格点。

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1007