Nested Ranges Count

题目描述

给定 n 个区间，你的任务是计算对于每个区间，它包含了多少其他区间以及被多少其他区间包含。 区间 $[a,b]$ 包含区间 $[c,d]$ 当且仅当 $a \le c$ 且 $d \le b$ 。

输入格式

第一行输入是一个整数 n：区间的数量。 接下来有 n 行描述这些区间。每行有两个整数 x 和 y：区间为 $[x,y]$ 。 你可以假设输入中不会出现重复的区间。

输出格式

第一行输出描述对于每个区间（按照输入顺序）它包含了多少其他区间。 然后输出一行描述对于每个区间（按照输入顺序）有多少其他区间包含它。

4
1 6
2 4
4 8
3 6

2 0 0 0
0 1 0 1

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x < y \le 10^9$

标签: CSES2169|排序和搜索

来源

CSES2169|排序和搜索