#P18249. Best Friend, Worst Enemy

Best Friend, Worst Enemy

Best Friend, Worst Enemy

题目描述

Bobo 正在分析一群人。第 i 个人有两个属性 x_i 和 y_i,不同人的属性对互不相同。

对于两个人 i≠j,定义他们的朋友指数和敌人指数:

$$\operatorname{Friend}(i,j)=\max(|x_i-x_j|,\ |y_i-y_j|),$$Enemy⁡(i,j)=∣xi−xj∣+∣yi−yj∣.\operatorname{Enemy}(i,j)=|x_i-x_j|+|y_i-y_j|.

在当前考虑的人中,如果对每个 k≠i 都有

$$\operatorname{Friend}(i,k)\ge\operatorname{Friend}(i,j),$$

则称 j 是 i 的一位最好的朋友。也就是说,朋友指数取最小值,允许并列。

如果对每个 k≠i 都有

$$\operatorname{Enemy}(i,k)\le\operatorname{Enemy}(i,j),$$

则称 j 是 i 的一位最坏的敌人。也就是说,敌人指数取最大值,同样允许并列。

现在,对每个 t=1,2,…,n,只考虑前 t 个人,求满足以下条件的有序数对 (i,j) 的数量:

  • 1≤i,j≤t,且 i≠j。
  • j 同时是 i 的一位最好的朋友和一位最坏的敌人。

请注意本题较小的空间限制。

输入格式

第一行包含一个整数 n。

接下来 n 行,第 i 行包含两个整数 x_i,y_i。

输出格式

输出 n 行,第 t 行包含一个整数,表示只考虑前 t 个人时,满足要求的有序数对数量。

数据范围

  • 2≤n≤400000。
  • 1≤x_i,y_i≤10000000。
  • 对任意 i≠j,保证 x_i≠x_j 或 y_i≠y_j,即没有两个完全相同的属性对。

不同人的某一个属性值可以相同。

样例 1

2
1 5
1 10
0
2

样例 2

4
2 5
5 3
5 7
8 5
0
2
4
4

样例 3

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

样例 4

13
3 5
4 4
4 5
4 6
5 3
5 4
5 5
5 6
5 7
6 4
6 5
6 6
7 5
0
2
4
7
2
2
5
2
2
3
3
4
4

样例说明

第一组样例中,只考虑第一个人时,没有符合条件的数对;考虑前两个人时,符合条件的是 (1,2) 和 (2,1)。

第二组样例中:

  • 只考虑第一个人时,答案为 0。
  • 考虑前两个人时,符合条件的是 (1,2)、(2,1)。
  • 考虑前三个人时,符合条件的是 (1,2)、(1,3)、(2,1)、(3,1)。
  • 考虑前四个人时,符合条件的是 (2,1)、(2,4)、(3,1)、(3,4)。