algorithm - 给定一个连续图。在 log(n) 中查找线段的交点数

Question

给定一个数组，例子：Arr[1 3 4 4 7 8 6 8 6 4 2]，其中10^10>Arr[i]>0，表示y坐标。x 坐标是它们对应的数组索引。通过连接 (i,Arr[i]) 和 (i+1,Arr[i+1) 等形成连续图。所以基本上它是通过连接直线形成的图形。给定一条从 x 范围（x1 到 x2）平行于 y 轴的线段。如果给定的线段通过一个交点，那么我们算作2个交点，除非相交线的左端点是（x2，y）或其右端点是（x1，y），那么我们只算1个交点. 我们可以通过这条线段 log(n) time 找到交叉点的数量吗？

标签： algorithmdata-structuresgraph

Answer 1

这是来自正在进行的比赛。再等一天的社论。