CF2002E.Cosmic Rays

给定一个整数数组 $s_1, s_2, \ldots, s_l$，每过一秒，宇宙射线会使所有满足 $i=1$ 或 $s_i\neq s_{i-1}$ 的 $s_i$ 同时被删除，剩下的部分会按顺序拼接成新的数组 $s_1, s_2, \ldots, s_{l'}$。

定义一个数组的“强度”为其变为空所需的秒数。

你得到的整数数组以 $n$ 个对的压缩形式给出，描述了从左到右的数组。每个对 $(a_i, b_i)$ 表示 $a_i$ 个 $b_i$，即 $\underbrace{b_i, b_i, \cdots, b_i}_{a_i\textrm{ 次}}$。

对于每个 $i=1,2,\dots,n$，请你求出由前 $i$ 个对描述的序列的强度。

每个测试包含多组测试用例。第一行包含测试用例个数 $t$（$1\le t\le 10^4$）。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1\le n\le 3\cdot10^5$）——序列 $a$ 的长度。

接下来的 $n$ 行，每行包含两个整数 $a_i$、$b_i$（$1\le a_i\le 10^9, 0\le b_i\le n$）——描述序列的对。

保证所有 $n$ 的总和不超过 $3\cdot10^5$。

保证对于所有 $1\le i<n$，都有 $b_i\neq b_{i+1}$。

对于每组测试用例，输出一行包含 $n$ 个整数，分别表示每个前缀对描述的序列的强度。

在第一个测试用例中，长度为 $4$ 的前缀对应的变化为 $[0,0,1,0,0,0,1,1,1,1,1]\rightarrow[0,0,0,1,1,1,1]\rightarrow[0,0,1,1,1]\rightarrow[0,1,1]\rightarrow[1]\rightarrow[]$，因此该数组在 $5$ 秒后变为空。

在第二个测试用例中，长度为 $4$ 的前缀对应的变化为 $[6,6,6,6,3,6,6,6,6,0,0,0,0]\rightarrow[6,6,6,6,6,6,0,0,0]\rightarrow[6,6,6,6,6,0,0]\rightarrow[6,6,6,6,0]\rightarrow[6,6,6]\rightarrow[6,6]\rightarrow[6]\rightarrow[]$，因此该数组在 $7$ 秒后变为空。

由 ChatGPT 4.1 翻译