Stars

题目描述:

给出一张星图(为一直角坐标系)，每一颗星用坐标(X,Y)表示。

现在定义第k颗星的level，等于除第k颗星外，其X<=X_k，且Y<=Y_k的星星数。

 

对于图中的星星5，其level=3，因为有3颗星星的坐标满足X<=X₅， Y<=Y₅（分别是星星1,2,4）。

 

 

输入格式:

第一行输入N，表示有N颗星星。(1<=N<=15000)

接下来N行每行输入一颗星星的坐标(X,Y)，(0<=X,Y<=32000)。坐标输入时没有任何顺序。

 

输出格式:

N行。第I行输出所有星星中，level=I-1的星星颗数。

样例输入:

5
1 1
5 1
7 1
3 3
5 5

样例输出:

1
2
1
1
0

提示:

大量数据，C++建议用scanf。

树状数组和线段树，各做一次。

时间限制: 1000ms
空间限制: 128MB

---