← 返回题目列表

Codeforces · 2042/D

D. 建议

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

假设您正在使用某些音频流服务。该服务拥有 $$$n$$$ 活跃用户和 $$$10^9$$$ 用户可以收听的曲目。用户可以喜欢曲目,并且根据喜欢,服务应该向他们推荐新曲目。

曲目编号从 $$$1$$$ 到 $$$10^9$$$。事实证明,跟踪第 $$$i$$$ 个用户的点赞形成了一个分段 $$$[l_i, r_i]$$$。

假设用户 $$$j$$$ 是用户 $$$i$$$ ($$$j \neq i$$$) 的预测器,如果用户 $$$j$$$ 喜欢第 $$$i$$$ 个用户喜欢的所有曲目(也可能还有其他一些曲目)。

另外,假设如果第 $$$i$$$ 个用户尚未喜欢某首曲目,但第 $$$i$$$ 个用户的每个预测者都喜欢该曲目,则强烈推荐该曲目给用户 $$$i$$$。

计算每个用户$$$i$$$的强烈推荐曲目数量。如果用户没有任何预测变量,则为该用户打印 $$$0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是 $$$t$$$ 案例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 用户数量。

接下来的 $$$n$$$ 行每行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) — 第 $$$i$$$ 个用户喜欢的曲目片段。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数,其中第 $$$i$$$ 个整数是第 $$$i$$$ 个用户强烈推荐的曲目数量(或 $$$0$$$,如果该用户没有任何预测变量)。

示例

输入 #1

4
3
3 8
2 5
4 5
2
42 42
1 1000000000
3
42 42
1 1000000000
42 42
6
1 10
3 10
3 7
5 7
4 4
1 2

输出 #1

0
0
1
999999999
0
0
0
0
0
2
3
2
4
8

注意

在第一个测试用例中:

- 第一个用户没有预测器;
- 第二个用户没有预测器;
- 第三个用户有两个预测变量:用户 $$$1$$$ 和 $$$2$$$;只有曲目 $$$3$$$ 被他们俩喜欢,而第三个用户不喜欢。

在第二个测试用例中,第二个用户是第一个用户的预测者。因此,除了 $$$42$$$ 之外,所有曲目均强烈推荐给第一个用户。

在第三个测试用例中,第一个用户有两个预测变量:用户 $$$2$$$ 和 $$$3$$$,但是没有他们喜欢而第一个用户自己不喜欢的曲目。