题目描述

定义星星的等级为它左下角的星星的数量 ( 即坐标满足x'≤x且y'≤y的星星数 )。 给你 n 个星星的坐标 ( 按先 y 递增，再 x 递增的顺序给 )，让你求出 0 ~ (n - 1) 各个等级星星的个数。

输入格式

第一行输入一个整数 n (0<n<=10000)。 第二行开始 n 行，每行两个数表示星星的坐标x,y。 数据保证 n 个星星的坐标，先按 y 递增，再 按 x 递增的顺序给。

输出格式

输出 n 行，表示 0 ~ (n - 1) 各个等级星星的个数。

样例

输入样例 1

5
1 1
5 1
7 1
3 3
5 5

输出样例 1

1 2 1 1 0

输入样例 2

1
0 0

输出样例 2

1

输入样例 3

2
0 0
1 0

输出样例 3

1 1

提示

思路：输入已按y升序排列，因此处理到第i个星星时，所有已处理的星星的y值均≤当前星星的y值。只需统计已处理星星中x值≤当前x的个数，即为当前星星的等级。 利用树状数组维护 x 坐标的出现次数。正序处理，每出现一个星星，先通过前缀和得到这个星星的等级并更新等级数组，再单点更新x坐标上星星的个数。 （因为 x 有 0 ，而树状数组不加 c[0] ，因此将 x + 1 后处理即可）