二维偏序

Stars

二维偏序问题可以概括为：双约束条件的元素统计问题。

一般的解法是：先固定一维，再用某种方法维护第二维。

题目描述

将星空看作一个平面，在平面上建立直角坐标系，这样平面上的每颗星星都有一个坐标。
天文学家定义了一颗星星的“水平”为：
- 在该星星正左边的星星数目、
- 正下方的星星数目、
- 以及左下方的星星数目之和。

输入格式

  • 第一行一个整数 $ N $，表示星星的数量。
  • 接下来 $ N $ 行，每行两个整数 $ x $ 和 $ y $，表示星星的横纵坐标。
  • 输入已按以下规则排序：
    • 按照 $ y $ 坐标升序排列；
    • 当 $ y $ 坐标相同时，按照 $ x $ 坐标升序排列。

输出格式

  • 每个水平对应的星星数量。

解决思路

这道题的数据已经按 $ y $ 坐标为第一关键词、$ x $ 坐标为第二关键词排好序了。
一般情况下，我们需要手动对点排序，排序的目的是：
- 确保所有可能小于当前点的点都在当前点之前被处理。

接着，我们将这些点的 $ x $ 坐标一个一个地压入树状数组。
由于点已按上述规则排序，我们只需利用树状数组动态维护前缀和，来快速统计左边和左下方的星星数量即可。

注意事项：
- 树状数组的下标需要从 1 开始，因此在处理时要特别留意。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define MAXN 15010
#define MAXM 32010
#define lowbit(x) ((x) & (-x))
// 树状数组
int tree[MAXM], ans[MAXN];
void update(int i, int x)
{
    for (; i <= MAXM; i += lowbit(i))
        tree[i] += x;
}
int query(int n)
{
    int ans = 0;
    for (; n; n -= lowbit(n))
        ans += tree[n];
    return ans;
}

int main()
{
    int n, x;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
       int x,y;
        cin>>x>>y;// 已经排好序了，y坐标可以不要了
        ans[query(x + 1)]++; // 统计
        update(x + 1, 1); // 更新，注意这两行都要+1
    }
    for (int i = 0; i < n; ++i)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}