← 返回题目列表

Codeforces · 1183/G

G. 糖果盒(硬版)

中文机器翻译题面 查看原题

该问题是同一竞赛中问题 D 的一个版本,带有一些额外的约束和任务。

糖果盒中有 $$$n$$$ 糖果。第 $$$i$$$ 糖果的类型为 $$$a_i$$$ ($$$1 \le a_i \le n$$$)。

您必须使用其中一些糖果来准备一份礼物,但有以下限制:礼物中每种类型的糖果数量应该完全不同(即,例如,包含两颗 $$$1$$$ 类型的糖果和两颗 $$$2$$$ 类型的糖果的礼物是不好的)。

礼物中可能完全没有多种类型的糖果。也有可能并非所有类型的糖果都会被当作礼物。

您确实很喜欢其中一些糖果,并且不想将它们包含在礼物中,但您想自己吃掉它们。对于每颗糖果,都会给出一个数字 $$$f_i$$$,如果您确实想为自己保留第 $$$i$$$ 颗糖果,则该数字等于 $$$0$$$;如果您不介意将其包含在礼物中,则等于 $$$1$$$。两种相同类型的糖果可能具有不同的 $$$f_i$$$ 值。

您希望您的礼物尽可能大,但又不想在礼物中包含太多您想吃的糖果。因此,您想要计算可以包含在礼物中的最大可能糖果数量,并且在选择最大糖果数量的所有方法中,您希望最大化礼物中具有 $$$f_i = 1$$$ 的糖果数量。

您必须回答 $$$q$$$ 独立查询。

如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。

输入

输入的第一行包含一个整数 $$$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$$$ 的糖果的最大数量。

示例

输入 #1

3
8
1 0
4 1
2 0
4 1
5 1
6 1
3 0
2 0
4
1 1
1 1
2 1
2 1
9
2 0
2 0
4 1
4 1
4 1
7 0
7 1
7 0
7 1

输出 #1

3 3
3 3
9 5

注意

在第一个查询中,您可以包含两颗 $$$4$$$ 类型的糖果和一颗 $$$5$$$ 类型的糖果。它们都有 $$$f_i = 1$$$ 并且您不介意将它们作为礼物的一部分赠送出去。