#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|),$$在当前考虑的人中,如果对每个 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)。