计算嵌套范围

Question

对于 [start, end] 形式的 N 个范围（包括两个端点），我想找到对于每个范围，有多少（其他）范围包含它以及它包含多少个范围（被它包含）。 tl;dr 统计每个范围包含的范围数量，并统计包含每个范围的范围数量。

这是 CSES 嵌套范围计数问题。

定义：范围 [s1, e1] 包含范围 [s2, e2] 当且仅当 s1 <= s2 and e2 <= e1.

N 是一个正整数，最大可达 2*10⁵。所有范围都有正整数端点，每个端点最多 10⁹。所有范围都是不同的。

时间限制为1秒。这是我的尝试，遗憾的是它没有通过，因为它太慢了。

#include <bits/extc++.h>
using namespace std;
int main() {
    cin.tie(0), ios::sync_with_stdio(0), cout.tie(0);
    int N;
    cin >> N;

    vector<pair<int, int>>ranges;
    while (N--) {
        int a, b;
        cin >> a >> b;
        ranges.emplace_back(a, b);
    }
    for (int i = 0; i < (int) ranges.size(); i++) {
        int cnt=0;
        for (int j = 0; j < (int) ranges.size(); j++)
            cnt += i != j && ranges[i].first <= ranges[j].first && ranges[j].second <= ranges[i].second;
        cout << cnt << ' ';
    }
    cout << '\n';
    for (int i = 0; i < (int) ranges.size(); i++) {
        int cnt =0;
        for (int j = 0; j < (int)ranges.size(); j++)
            cnt += i != j && ranges[j].first <= ranges[i].first && ranges[i].second<= ranges[j].second;
        cout << cnt << ' ';
    }
}

输入示例：

4
1 6
2 4
4 8
3 6

输出示例：

2 0 0 0
0 1 0 1

说明：输出的第一行包含每个范围包含的范围数，按照范围在输入中的顺序排列，用空格分隔。 第二行包含包含每个范围的范围数，顺序相同。

如何更有效地解决这个问题（客观上：在时限内）？我错过了一些算法吗？

Answer 1

我尝试解决这个问题。我的方法类似，但与 YouTube 视频中显示的方法有点不同 https://www.youtube.com/watch?v=ORdmSirqrMs 因为我想使用 c 并且只使用我自己的数据结构。

“技巧”是使用一种数据结构，该结构可以有效地为您提供插入元素的索引位置，就像它们位于有序列表中一样。我主要用c语言编程，而c语言本身不支持复杂的数据结构，所以我实现了一个二叉搜索树（BST），它允许我插入元素并在插入后返回树中元素的数量，其中元素的数量较少大于、等于和大于我插入的值。我分别将它们表示为 lt、eq 和 gt。 BST 对于时间复杂度为 O(log n) 的足够随机插入效果很好，但如果没有某种形式的自平衡，它的最坏情况插入时间为 O(n)。例如，假设我插入了 10、34、67、132 和 15，然后在插入另一个元素 66 后，我得到 lt = 3, eq = 1, gt = 2。

我使用的算法如下。

Sort Ranges on s_i ascending, e_i descending
CountingBSTinit();
for (i=0; i<Rangessize; i++) {
  CountingBSTinsert(&lt, &eq, &gt, Ranges[i].e);
  Ranges[i].contained = gt + eq - 1;
}
CountingBSTfree();
CountingBSTinit();
for (i=Rangessize-1; i>=0; i--) {
  CountingBSTinsert(&lt, &eq, &gt, Ranges[i].e);
  Ranges[i].contains = lt + eq - 1;
}
Unsort Ranges

我按照问题陈述中的描述创建了一个包含 200,000 个随机范围的数组，并在我的旧 Westmere 笔记本电脑上用不到 1 秒的时间解决了这个问题。我将结果与简单的 O(n^2) 算法产生的结果进行了比较，该算法花费了 2m 45s，慢了 150 倍以上。

这就是我实现 BST 计数版本的方法。如果一个节点上有 lt、eq 和 gt，那么在父节点上，它应该更新为

if left node
  (lt, eq, gt) = (lt, eq, gt + parenteq + parentgt) 
  parentlt++
else 
  (lt, eq, gt) = (lt + parenteq + parentlt, eq, gt) 
  parentgt++

当您从插入的节点向上移回树时。我认为这可以更有效地完成，这样您就不必返回树上，但这就是我所做的。额外的节点遍历不会改变插入的时间复杂度，并且如果访问的节点仍在缓存中，则修改算法可能不会带来什么性能优势。