题意

每个电台有属性 \((x_i,r_i,f_i)\) ,求满足 \(min(r_i,r_j)\ge |x_i-x_j|,i<j,|f_i-f_j|\le k\) 的数对 \((i,j)\) 有多少。

分析

如果我们按照 \(r\) 从大到小排序,那么针对每一个 \(r_i\) ,我们需要找到所有的 \(j(j<i)\) 满足 \(r_i\ge |x_i-x_j|,|f_i-f_j|\le k\) ,即 \(x_i-r_i\le x_j\le r_i+x_i\) 且 \(f_i-k\le f_j\le k+f_i\) 。

针对每一个 \(i\) ,显然不等式的两边都是常量,于是题目转化成了求子矩阵内的点,即二维数点问题。

经典的三维偏序问题,对所有的坐标离散,然后利用归并排序对第二维(横坐标)排序以后,用树状数组维护第三维(纵坐标),统计数量即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注