CF1974F.Cutting Game

Alice 和 Bob 又在玩游戏了。他们有一个大小为 $a \times b$ 的网格（$1 \le a, b \le 10^9$），网格上有 $n$ 个棋子，每个格子最多有一个棋子。第 $x$ 行第 $y$ 列的格子的坐标为 $(x, y)$。

Alice 先手，之后两人轮流操作。每次操作时，玩家可以从当前剩余网格的开头或结尾裁去若干（但不是全部）行或列，并且每裁去一颗棋子就获得 1 分。每次操作可以用一个字符 'U'、'D'、'L' 或 'R' 和一个整数 $k$ 来描述：

• 如果字符为 'U'，则裁去当前剩余网格的前 $k$ 行；
• 如果字符为 'D'，则裁去当前剩余网格的后 $k$ 行；
• 如果字符为 'L'，则裁去当前剩余网格的前 $k$ 列；
• 如果字符为 'R'，则裁去当前剩余网格的后 $k$ 列。

根据初始网格状态和玩家的操作，求 Alice 和 Bob 分别获得的分数。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例数量。

每个测试用例的第一行包含四个整数 $a$、$b$、$n$ 和 $m$（$2 \le a, b \le 10^9$，$1 \le n, m \le 2 \times 10^5$）——网格的行数、列数、棋子数和操作数。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le a$，$1 \le y_i \le b$）——每个棋子的坐标。所有坐标对均不相同。

接下来的 $m$ 行，每行包含一个字符 $c_j$ 和一个整数 $k_j$——第 $j$ 次操作的描述。保证 $k$ 小于当前网格剩余的行数或列数，即玩家不能一次裁去所有剩余的行或列。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$，所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出两个整数，分别表示 Alice 和 Bob 获得的分数。

以下是第一个样例的游戏过程：

Alice 首先从底部裁去 $2$ 行，获得 $2$ 分，然后 Bob 从右侧裁去 $1$ 列，获得 $1$ 分。注意，如果 Bob 从底部裁去 $1$ 行，也会获得 $1$ 分。

由 ChatGPT 4.1 翻译