CF1051G Distinctification

给定一个长度为 $k$ 的整数对序列 $S$，其中每个元素为 $(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)$。 你可以对该序列进行如下操作： 1. 选择某个位置 $i$，将 $a_i$ 增加 $1$。只有当存在至少一个 $j$ 满足 $i \ne j$ 且 $a_i = a_j$ 时，才能进行此操作。该操作的代价为 $b_i$； 2. 选择某个位置 $i$，将 $a_i$ 减少 $1$。只有当存在至少一个 $j$ 满足 $a_i = a_j + 1$ 时，才能进行此操作。该操作的代价为 $-b_i$。 每种操作可以执行任意次（包括零次）。 设 $f(S)$ 为使得经过一系列操作后，所有 $a_i$ 两两不同时，总代价的最小可能值 $x$。 现在，给定一个长度为 $n$ 的整数对序列 $P$，其中 $P = (a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$，且所有 $b_i$ 两两不同。记 $P_i$ 为 $P$ 的前 $i$ 个元素组成的序列。你的任务是计算 $f(P_1), f(P_2), \dots, f(P_n)$ 的值。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示序列 $P$ 的长度。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le 2 \cdot 10^5$，$1 \le b_i \le n$）。保证所有 $b_i$ 两两不同。

输出 $n$ 个整数，第 $i$ 个数表示 $f(P_i)$ 的值。

由 ChatGPT 4.1 翻译