CF1183G Candy Box (hard version)

本题是同场比赛中 D 题的一个变种，增加了一些额外的限制和任务。 有 $n$ 颗糖果放在一个糖果盒中。第 $i$ 颗糖果的类型为 $a_i$（$1 \le a_i \le n$）。 你需要用这些糖果中的一部分来准备一份礼物，满足以下限制：在礼物中，每种类型的糖果数量必须互不相同（例如，包含两颗 1 型糖果和两颗 2 型糖果的礼物是不合法的）。 某些类型的糖果可以完全不出现在礼物中。某些类型的糖果也可以只取其中一部分放入礼物。 你特别喜欢其中一些糖果，不想把它们放进礼物，而是想自己吃。对于每颗糖果，给定一个数 $f_i$，如果 $f_i = 0$，表示你想自己留着第 $i$ 颗糖果；如果 $f_i = 1$，表示你不介意把它放进礼物。同一种类型的两颗糖果，$f_i$ 的值可能不同。 你希望礼物中糖果的数量尽可能多，但又不想把太多自己想吃的糖果放进礼物。因此，你需要计算在满足条件的情况下，礼物中最多能包含多少颗糖果；在所有能达到最大数量的方案中，你还希望礼物中 $f_i = 1$ 的糖果数量尽可能多。 你需要回答 $q$ 个独立的询问。 如果你使用 Python 编程，建议提交时使用 PyPy 以提高运行效率。

输入的第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问的数量。 每个询问的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示糖果的数量。 接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $f_i$（$1 \le a_i \le n$，$0 \le f_i \le 1$），其中 $a_i$ 表示第 $i$ 颗糖果的类型，$f_i$ 表示你是否想自己留着第 $i$ 颗糖果（$0$ 表示想留着，$1$ 表示不介意送出）。 保证所有询问中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个询问，输出两个整数： - 礼物中最多能包含的糖果数量； - 在所有能达到最大数量的方案中，礼物中 $f_i = 1$ 的糖果数量的最大值。

在第一个询问中，你可以选择两颗 4 型糖果和一颗 5 型糖果，它们的 $f_i$ 都为 $1$，你不介意把它们送出去作为礼物。 由 ChatGPT 4.1 翻译