二维点集支配点计数（等级计算）的C++代码优化咨询

问题背景 #

需要对给定二维点集计算每个点的等级：点的等级为x、y坐标均小于等于该点的点的总数量，最终统计每个等级对应的点个数。点的最大数量为15000，现有两种实现均无法满足运行效率要求。

现有实现问题分析 #

暴力实现 #

#include <iostream>
using namespace std;

int N, x[15005], y[15005], level[15005] = {0};

int main()
{
  cin >> N;

  for (int i = 0; i < N; i++) cin >> x[i] >> y[i];

  for (int i = 0; i < N; i++) {
    int count = 0;

    for (int j = 0; j < N; j++)
      if (y[i] >= y[j] && x[i] >= x[j])
        count++;

    level[count]++;
  }

  for (int i = 1; i <= N; i++) cout << level[i] << endl;
}

该实现采用双重循环两两比对，时间复杂度为O(n²)，n=15000时总运算量达2.25亿次，很容易超出时间限制。

初步排序优化版本 #

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int N, X, Y, level[15005] = {0};
pair<int, int> points[15005];

int main()
{
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> X >> Y;
    points[i] = make_pair(X, Y);
  }

  sort(points, points + N, [](const pair<int, int> &a, const pair<int, int> &b)
       { return a.first > b.first; });

  for (int i = 0; i < N; i++) {
    int count = 0;

    for (int j = 0; j < N; j++)
      if (points[i].first >= points[j].first && points[i].second >= points[j].second)
        count++;

    level[count]++;
  }

  for (int i = 1; i <= N; i++) cout << level[i] << endl;
}

该版本虽然对点按x做了降序排序，但内层循环依然遍历全部点做双条件判断，时间复杂度仍为O(n²)，排序带来的有序性完全没有被利用，因此性能没有本质提升。

优化方案 #

核心思路是将二维条件判断降为一维，用高效数据结构把线性统计替换为对数级统计：

• 首先将所有点按x坐标升序排序，x坐标相同的点按y坐标升序排序。排序完成后，处理第i个点时，所有排在i前面的点x坐标必然小于等于当前点x，此时只需要统计已处理点中y坐标小于等于当前点y的数量，加上当前点自身就是该点的等级，无需再判断x维度条件。
• 用树状数组（Fenwick Tree）维护已处理点的y坐标计数，支持O(logM) 复杂度的单点更新（插入新点的y值）和前缀和查询（统计y≤当前值的点总数），M为y坐标的取值范围。

整体时间复杂度可降到O(nlogn)，n=15000时总运算量仅20万次左右，性能提升上千倍。

优化后实现代码 #

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

const int MAXN = 15005;
// 若y最大值超过32000可调整该值，若y范围过大可先做离散化
const int MAXY = 32005;
int N, level[MAXN] = {0};
pair<int, int> points[MAXN];
int tree[MAXY];

int lowbit(int x) {
    return x & -x;
}

// 树状数组单点更新
void update(int idx, int val) {
    while (idx < MAXY) {
        tree[idx] += val;
        idx += lowbit(idx);
    }
}

// 树状数组前缀和查询，返回[1, idx]区间的总和
int query(int idx) {
    int res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= lowbit(idx);
    }
    return res;
}

int main()
{
    // 关闭cin同步加速输入
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> points[i].first >> points[i].second;
        // 树状数组下标从1开始，若y可能取0则统一+1偏移，避免下标0导致死循环
        points[i].second++;
    }

    sort(points, points + N, [](const pair<int, int> &a, const pair<int, int> &b) {
        if (a.first == b.first) return a.second < b.second;
        return a.first < b.first;
    });

    for (int i = 0; i < N; i++) {
        int curY = points[i].second;
        int cnt = query(curY);
        // 等级计数从1开始，包含当前点自身
        level[cnt + 1]++;
        update(curY, 1);
    }

    for (int i = 1; i <= N; i++) {
        // 用'\n'代替endl，避免频繁刷新缓冲区提升输出速度
        cout << level[i] << '\n';
    }
    return 0;
}

补充说明 #

• 如果题目中y坐标取值范围远大于点的数量，可以先收集所有点的y值，排序去重后做离散化映射，压缩树状数组的空间大小，进一步提升运行效率。
• 除了树状数组，也可以用线段树实现相同的单点更新、前缀查询逻辑，但树状数组代码更短、常数更小，更适合这类场景。

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