好的，这是我在高级算法课上遇到的问题。我已经提交过一次解决方案，但由于效率问题被导师拒绝，换句话说，我已经付出了努力，但即使在他的提示下也无法得到，所以请温柔。我将在下面给出他的提示
给定一个包含起点和终点的区间数组，找出每个区间的其他区间数。间隔数小于 10^9 并且它们的 id 是不同的。start 和 end 小于 10^18，输入文件不包含重复的 start 和 end 数字。上面所有的数字都是整数
提示是：考虑带有桶的数据结构。该算法应该比 O(n^2) 快
sample input and output
input:
5 %% number of intervals
2 100 200 %% id, start,end. all lines below follows this
3 110 190
4 105 145
1 90 150
5 102 198
output:
3 0
4 0
1 1
5 2
2 3
这些数字非常大，所以 O(N log N) 可能有点多，但这里有一个想法。
首先要对值进行标准化，这意味着在保持相同顺序的同时将它们变小。在您的示例中，规范化将是
90 100 102 105 110 145 150 190 198 200
1 2 3 4 5 6 7 8 9 10
所以你的新间隔是：
5
2 2 10
3 5 8
4 4 6
1 1 7
5 3 9
现在区间的边缘在 [1, 2N] 的范围内。
现在按它们的结尾对间隔进行排序：
5
4 4 6
1 1 7
3 5 8
5 3 9
2 2 10
当你到达一个区间时，你可以说在它之前开始但尚未遇到的所有区间的答案都应该加一。这可以通过 SegmentTree 来完成。
当您获得区间 [x, y] 时，您会将 [1, x - 1] 范围内的所有值增加 1，然后将其答案计算为线段树中 x 处的值。这只是一个区间的加法和一个点的查询，一个常见的段树问题。
我真的不认为你可以用少于 O(N log N) 的时间和 O(N) 的内存来解决这个问题，所以这个解决方案应该是时间和空间上的渐近最佳解决方案。