「一本通 4.1 例 2」数星星 Stars

题目描述

天空中有 $N$ 颗互不重叠的星星。若某颗星星左下方（含正左、正下）有 $k$ 颗星星，则称它是 $k$ 级的。给定按 $y$ 增序给出（ $y$ 相同按 $x$ 增序）的 $N$ 个点，求 $0\sim N-1$ 级各有多少颗星星。

输入第一行 $N$ ，随后 $N$ 行每行两个整数 $x_i, y_i$ ；输出 $N$ 行，第 $k+1$ 行是 $k$ 级星星的数目。 $1\le N\le 1.5\times10^4$ ， $0\le x,y\le 3.2\times10^4$ 。样例输入 5 / 1 1 / 5 1 / 7 1 / 3 3 / 5 5，样例输出 1 / 2 / 1 / 1 / 0。

思路

输入已按 $y$ 增序给出，处理到某颗星星时，此前读入的星星其 $y$ 都不超过它，因此只需统计其中 $x\le x_i$ 的星星数即为该星等级。用树状数组维护各横坐标出现的次数，每颗星星做一次前缀和查询与一次单点加一即可，复杂度 $O(N\log M)$ 。

参考代码

Python 版：

python

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
38
39
40
41
42
43
44
45
46
47
48
49
50#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 16:55
# update_at: 2026-09-30 16:55

import sys

MAX_X = 32001  # x 坐标最大为 32000，转为 1-based 下标最大 32001


def add(tree: list[int], idx: int, delta: int) -> None:
    """在树状数组 idx 位置增加 delta。"""
    while idx < len(tree):
        tree[idx] += delta
        idx += idx & -idx


def query(tree: list[int], idx: int) -> int:
    """查询树状数组前缀和 [1, idx]。"""
    res = 0
    while idx > 0:
        res += tree[idx]
        idx -= idx & -idx
    return res


def count_star_levels(n: int, coords: list[tuple[int, int]]) -> list[int]:
    """按给出顺序依次统计每颗星星的等级分布。"""
    tree = [0] * (MAX_X + 1)
    level_counts = [0] * n
    for x, _ in coords:
        pos = x + 1  # 树状数组下标从 1 开始
        level = query(tree, pos)
        level_counts[level] += 1
        add(tree, pos, 1)
    return level_counts


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    coords = [(next(data), next(data)) for _ in range(n)]
    ans = count_star_levels(n, coords)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:35
 * update_at: 2026-10-06 00:35
 */
#include <cstdio>

typedef long long ll;

const int MAXX = 32000;          // 横坐标最大值
const int MAXN = 15000;          // 星星数量上限
int tree[MAXX + 2];              // 树状数组，维护各横坐标出现次数
ll level_cnt[MAXN + 1];          // level_cnt[k] = 等级为 k 的星星数量

// 在位置 pos 上加 1。
void add(int pos) {
    while (pos <= MAXX + 1) {
        tree[pos]++;
        pos += pos & -pos;
    }
}

// 查询前缀和 [1, pos]，即横坐标不超过 pos-1 的已读入星星数。
int query(int pos) {
    int res = 0;
    while (pos > 0) {
        res += tree[pos];
        pos -= pos & -pos;
    }
    return res;
}

int main() {
    ll n;
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        // 输入已按 y 增序给出，故此前读入的点 y 均不超过当前点，
        // 只需统计横坐标不超过 x 的点数即为等级。
        int pos = x + 1;         // 树状数组下标从 1 开始
        int level = query(pos);
        level_cnt[level]++;
        add(pos);
    }
    for (ll k = 0; k <= n - 1; k++) {
        printf("%lld\n", level_cnt[k]);
    }
    return 0;
}

「一本通 4.1 例 2」数星星 Stars

目录

题目描述

思路

参考代码