CSES嵌套区间计数问题：暴力解法超时，求高效优化方案

问题描述 #

给定N个形如[start, end]的区间（两端点均包含），需为每个区间计算两个值：

• 包含其他区间的数量：满足s_i ≤ s_j且e_j ≤ e_i的区间j的个数（j≠i）
• 被其他区间包含的数量：满足s_j ≤ s_i且e_i ≤ e_j的区间j的个数（j≠i）

约束条件：

• N最大为2×10⁵
• 区间端点最大为10⁹
• 所有区间互不相同
• 时间限制1秒

暴力解法（超时） #

以下是暴力枚举的实现，时间复杂度为O(N²)，无法通过大数据测试：

#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

样例解释 #

• 第一行：每个区间包含的其他区间数量，按输入顺序排列。比如第一个区间[1,6]包含[2,4]和[3,6]，所以是2。
• 第二行：每个区间被其他区间包含的数量，按输入顺序排列。比如第二个区间[2,4]被[1,6]包含，第四个区间[3,6]被[1,6]包含，所以分别是1和1。

高效解法思路 #

核心思路是排序+离散化+树状数组（Fenwick Tree），将时间复杂度优化到O(N log N)，符合时间限制。

1. 离散化处理 #

由于区间端点最大为10⁹，无法直接用作树状数组的下标，因此需要将所有区间的end值离散化，映射到1~N的连续整数区间。

2. 计算「包含其他区间的数量」 #

• 排序规则：将区间按start升序排列，若start相同，则按end降序排列。这样保证当处理到某个区间时，所有start大于等于它的区间都在后续遍历位置。
• 遍历方式：从后往前遍历排序后的区间，用树状数组维护已遍历区间的end值。对于当前区间，查询树状数组中end小于等于当前区间end的数量，即为当前区间包含的其他区间数。之后将当前区间的end加入树状数组。

3. 计算「被其他区间包含的数量」 #

• 排序规则：将区间按start升序排列，若start相同，则按end升序排列。这样保证当处理到某个区间时，所有start小于等于它的区间都在前面的遍历位置。
• 遍历方式：从前往后遍历排序后的区间，用树状数组维护已遍历区间的end值。对于当前区间，查询树状数组中end大于等于当前区间end的数量（可通过总已遍历数减去end小于当前区间end的数量得到），即为当前区间被包含的数量。之后将当前区间的end加入树状数组。

注意点 #

• 所有操作需保留区间的原始索引，确保计算结果能对应到输入顺序输出。

高效解法代码实现 #

#include <bits/stdc++.h>
using namespace std;

struct FenwickTree {
    vector<int> tree;
    int n;

    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void update(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<tuple<int, int, int>> ranges(N); // (start, end, original index)
    vector<int> ends;

    for (int i = 0; i < N; ++i) {
        int s, e;
        cin >> s >> e;
        ranges[i] = {s, e, i};
        ends.push_back(e);
    }

    // 离散化end值
    sort(ends.begin(), ends.end());
    ends.erase(unique(ends.begin(), ends.end()), ends.end());
    auto get_idx = [&](int e) {
        return lower_bound(ends.begin(), ends.end(), e) - ends.begin() + 1; // 树状数组从1开始
    };
    int m = ends.size();

    // 计算包含其他区间的数量
    vector<int> contains(N, 0);
    sort(ranges.begin(), ranges.end(), [](const auto& a, const auto& b) {
        if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
        return get<1>(a) > get<1>(b);
    });
    FenwickTree ft1(m);
    for (int i = N - 1; i >= 0; --i) {
        int e = get<1>(ranges[i]);
        int idx = get_idx(e);
        contains[get<2>(ranges[i])] = ft1.query(idx);
        ft1.update(idx, 1);
    }

    // 计算被其他区间包含的数量
    vector<int> contained(N, 0);
    sort(ranges.begin(), ranges.end(), [](const auto& a, const auto& b) {
        if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
        return get<1>(a) < get<1>(b);
    });
    FenwickTree ft2(m);
    for (int i = 0; i < N; ++i) {
        int e = get<1>(ranges[i]);
        int idx = get_idx(e);
        // 已插入的数量是i，减去query(idx-1)就是>=e的数量
        contained[get<2>(ranges[i])] = i - ft2.query(idx - 1);
        ft2.update(idx, 1);
    }

    // 输出结果
    for (int x : contains) cout << x << ' ';
    cout << '\n';
    for (int x : contained) cout << x << ' ';
    cout << '\n';

    return 0;
}

代码说明 #

• FenwickTree实现了树状数组的基本操作：单点更新和前缀查询。
• 离散化通过排序+去重实现，将大范围的end值映射到小范围的索引。
• 两次排序分别对应两种统计需求，通过原始索引将结果映射回输入顺序。

内容的提问来源于stack exchange，提问作者user24044002