P17085 [COTS 2026] 原子 / Atomi（暂无数据）

2s, 512M

有 $N$ 个原子排成一排，从左往右依次编号 $1\sim N$。原子 $i$ 质量为 $w_i$，初始移动方向为向左或向右。 所有原子同时开始向其初始方向移动。相邻原子之间的距离相等，并且所有原子都以相同的速率匀速移动。 当质量为 $x$ 和 $y$ 的两个原子碰撞时，会发生核聚变，它们合并为一个质量为 $x + y$ 的新原子。新原子继续向碰撞的两个原子中较重的一个的方向移动。如果它们的质量相等，新原子向右移动。 经过足够长的时间后，将不再发生碰撞。将剩余的原子分为两组：向左移动和向右移动。我们想知道第一组原子的总质量和第二组原子的总质量。 你需要回答 $Q$ 个询问。第 $i$ 个询问给定两个数字 $l_i$ 和 $r_i$，若只观察原子 $l_i, l_i + 1, \dots , r_i$（忽略其他原子）时，两组原子分别的总质量。 对于每个询问，输出最终向左移动的原子的总质量和最终向右移动的原子的总质量。

第一行包含一个正整数 $N$（$1 \le N \le 3 \cdot 10^5$），表示原子的数量。 接下来 $N$ 行中的第 $i$ 行包含一个正整数 $w_i$（$1 \le l_i \le r_i \le N$）和一个字符 $c_i$（$c_i\in \{\texttt{L},\texttt{R}\}$），分别表示第 $i$ 个原子的质量和初始方向。字符 $c_i$ 为 `L` 表示原子一开始向左移动，或者为 `R` 表示向右移动。 下一行包含一个正整数 $Q$（$1 \le Q \le 3 \cdot 10^5$），表示询问的数量。 接下来 $Q$ 行中的第 $i$ 行包含两个正整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le N$），表示第 $i$ 个询问中原子子段的边界。

对于每个询问，输出两个整数：最终向左移动的原子的总质量，以及最终向右移动的原子的总质量。

### 样例解释 以下为样例 $1$ 解释。 在第一个询问中，我们观察所有五个原子。第二和第三个原子合并成一个质量为 $6$ 并向左移动的原子，第四和第五个原子合并成一个质量为 $8$ 并向右移动的原子。第一个原子继续向左移动，所以答案是 $11$ 和 $8$。 在第四个询问中，我们观察第三和第四个原子。由于它们向相互背离的方向移动，它们不会相撞，所以答案是 $4$ 和 $7$。 ### 子任务 | 子任务 | 分数 | 限制 | |:---:|:---:|---| | $1$ | $11$ | $N, Q \le 1\,000$ | | $2$ | $9 $| 对于每个询问 $i$，$l_i = 1$。 | | $3$ | $10$ | 初始时恰好只有一个原子向右移动。 | | $4$ | $24$ | 存在 $0 \le k \le N$，使得原子 $1, \dots, k$ 向右移动，而原子 $k + 1, \dots, N$ 向左移动。 | | $5$ | $21$ | $N \le 3 \cdot 10^4$ | | $6$ | $25$ | 无附加限制。 |