如何优化std::vector数对中满足首值大于X且次值大于Y的数对计数查询？

嘿，你的暴力遍历解法在n和q都达到1e5的时候肯定会超时——毕竟O(q*n)的复杂度意味着1e10次操作，这远远超出了时间限制。下面给你一套高效的优化方案，核心思路是离线处理查询加上Fenwick树（树状数组），能把时间复杂度降到O((n+q)log(n+q))，完全能处理1e5级别的数据。

核心思路 #

我们把所有数对和查询都先排序，然后用树状数组动态维护符合条件的元素，批量处理查询，避免重复遍历。具体步骤如下：

1. 预处理：离散化+排序 #

• 离散化Y值：因为数对的第二个元素和查询的Y可能范围极大（比如到1e9），直接用树状数组存不下。我们把所有出现过的Y（包括数对的第二个元素和所有查询的Y）收集起来，排序去重后给每个Y分配一个唯一的排名，把大数值范围压缩到我们能处理的大小（最多2e5个元素）。
• 排序数对：把所有数对按第一个元素降序排列，如果第一个元素相同，第二个元素也降序排列。这样我们可以按顺序把首元素足够大的数对加入树状数组。
• 排序查询：把所有查询按X降序排列，同时保存每个查询的原始索引，这样最后能把结果对应回原来的查询顺序。

2. 离线处理查询 #

• 初始化一个空的Fenwick树，大小为离散化后的排名总数。
• 用一个指针指向排序后的数对列表开头，遍历每个排序后的查询：
  • 把所有首元素>当前查询X的数对，将它们的第二个元素的离散化排名插入树状数组（也就是在对应位置加1）。
  • 现在树状数组里的所有元素都是首元素>X的数对的第二个元素。我们需要统计其中大于Y的数量：用树状数组里的总元素数，减去小于等于Y的元素数量（通过树状数组的前缀和查询得到），就是我们要的结果。
  • 把结果存到结果数组的对应原始索引位置。

3. 输出结果 #

最后按原始查询的顺序输出结果数组即可。

代码实现（C++） #

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

// Fenwick Tree 实现，用于高效的前缀和查询和单点更新
struct FenwickTree {
    vector<int> tree;
    int n;

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

    // 在idx位置增加delta（idx从1开始）
    void update(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    // 查询1到idx的前缀和
    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    // 加速输入输出，处理1e5规模数据必备
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int, int>> pairs(n);
    vector<int> all_ys;

    // 读取数对，收集所有Y值
    for (int i = 0; i < n; ++i) {
        cin >> pairs[i].first >> pairs[i].second;
        all_ys.push_back(pairs[i].second);
    }

    int q;
    cin >> q;
    // 存储查询：X, Y, 原始索引
    vector<tuple<int, int, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        int X, Y;
        cin >> X >> Y;
        queries[i] = {X, Y, i};
        all_ys.push_back(Y);
    }

    // 离散化Y值：排序+去重
    sort(all_ys.begin(), all_ys.end());
    all_ys.erase(unique(all_ys.begin(), all_ys.end()), all_ys.end());
    // 获取Y对应的排名（从1开始）
    auto get_rank = [&](int y) {
        return lower_bound(all_ys.begin(), all_ys.end(), y) - all_ys.begin() + 1;
    };

    // 按首元素降序排序数对，首元素相同则按次元素降序
    sort(pairs.begin(), pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second > b.second;
    });

    // 按X降序排序查询，这样可以批量处理符合条件的数对
    sort(queries.begin(), queries.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
        return get<0>(a) > get<0>(b);
    });

    FenwickTree ft(all_ys.size());
    vector<int> ans(q);
    int pair_ptr = 0; // 指向当前要处理的数对

    for (const auto& qry : queries) {
        int X = get<0>(qry);
        int Y = get<1>(qry);
        int original_idx = get<2>(qry);

        // 把所有首元素>X的数对加入树状数组
        while (pair_ptr < n && pairs[pair_ptr].first > X) {
            int rank = get_rank(pairs[pair_ptr].second);
            ft.update(rank, 1);
            pair_ptr++;
        }

        // 计算大于Y的数量：总元素数 - 小于等于Y的元素数
        int total_valid = pair_ptr;
        int y_rank = get_rank(Y);
        int cnt_less_or_eq = ft.query(y_rank);
        ans[original_idx] = total_valid - cnt_less_or_eq;
    }

    // 按原始顺序输出结果
    for (int result : ans) {
        cout << result << '\n';
    }

    return 0;
}

关键注意事项 #

• 离散化的完整性：一定要把所有数对的第二个元素和查询的Y都包含进去，否则会出现找不到排名的情况。
• 树状数组的索引：树状数组的实现通常从1开始，所以离散化后的排名也要从1开始，避免0索引导致的错误。
• 输入输出加速：对于1e5级别的数据，必须用ios::sync_with_stdio(false);和cin.tie(nullptr);来关闭同步，否则输入输出会很慢。
• 负数处理：如果Y可能是负数，离散化的方法依然适用，因为排序和去重不区分正负。

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