首页 > 其他分享 >NC50428 数星星 Stars

NC50428 数星星 Stars

时间:2023-04-28 09:47:35浏览次数:63  
标签:星星 rt return int sum NC50428 数星星 坐标 Stars

题目链接

题目

题目描述

天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。如果一个星星的左下方(包含正左和正下)有k颗星星,就说这颗星星是k级的。

stars1.png

例如,上图中星星5是3级的(1,2,4在它左下),星星2,4是1级的。例图中有1个0级,2个1级,1个2级,1个3级的星星。

给定星星的位置,输出各级星星的数目。
一句话题意 给定n个点,定义每个点的等级是在该点左下方(含正左、正下)的点的数目,试统计每个等级有多少个点。

输入描述

第一行一个整数N,表示星星的数目;
接下来N行给出每颗星星的坐标,坐标用两个整数x,y表示;
不会有星星重叠。星星按y坐标增序给出,y坐标相同的按x坐标增序给出。

输出描述

N行,每行一个整数,分别是0级,1级,2级,……,N-1级的星星的数目。

示例1

输入

5
1 1
5 1
7 1
3 3
5 5

输出

1
2
1
1
0

备注

对于全部数据, \(1 \le N \le1.5 \times 10^4,0 \le x,y \le 3.2 \times10^4\) 。

题解

知识点:线段树。

直接求每颗星星左下角的星星个数是二维询问,比较困难(但貌似也可以用二维数据结构维护)。

对于每个星星,我们希望询问能在一维上完成,这样就能很方便的用一些数据结构实现。不妨考虑压缩掉 \(y\) 轴,将星星映射到一条水平直线上,就可以很方便的用权值线段树询问星星左侧的星星个数。

之后我们还需要解决一个问题,如何只询问一颗星星左侧下方的,而不是左侧全部的星星个数。显然,只通过线段树是无法做到的,因为能有效维护的信息有限。

不妨考虑在输入顺序上动手脚,我们只要保证询问一颗星星的时候,其左侧只存在 \(y\) 坐标小于等于它自己的全部星星就行,将此时询问作为答案。因此,我们考虑对输入按 \(y\) 升序排序,若 \(y\) 相同则按 \(x\) 升序排序,这样保证输入的这个星星之前的星星, \(y\) 坐标一定不超过自己,且保证 \(x\) 不超过自己的星星已经全部输入。

至此,对于这道题的偏序关系,我们只需要离线安排输入顺序(这道题其实一开始输入顺序已经帮你安排好了),即可有效减少一个维护维度。

时间复杂度 \(O((n+32000) \log (32000))\)

空间复杂度 \(O(n+32000)\)

代码

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

struct T {
    int sum;
    static T e() { return { 0 }; }
    friend T operator+(const T &a, const T &b) { return { a.sum + b.sum }; }
};
struct F {
    int add;
    T operator()(const T &x) { return { x.sum + add }; }
};

template<class T, class F>
class SegmentTree {
    int n;
    vector<T> node;

    void update(int rt, int l, int r, int x, F f) {
        if (r < x || l > x) return;
        if (l == r) return node[rt] = f(node[rt]), void();
        int mid = l + r >> 1;
        update(rt << 1, l, mid, x, f);
        update(rt << 1 | 1, mid + 1, r, x, f);
        node[rt] = node[rt << 1] + node[rt << 1 | 1];
    }

    T query(int rt, int l, int r, int x, int y) {
        if (r < x || l > y) return T::e();
        if (x <= l && r <= y) return node[rt];
        int mid = l + r >> 1;
        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
    }

public:
    SegmentTree(int _n = 0) { init(_n); }
    SegmentTree(int _n, const vector<T> &src) { init(_n, src); }
    void init(int _n) {
        n = _n;
        node.assign(n << 2, T::e());
    }
    void init(int _n, const vector<T> &src) {
        init(_n);
        function<void(int, int, int)> build = [&](int rt, int l, int r) {
            if (l == r) return node[rt] = src[l], void();
            int mid = l + r >> 1;
            build(rt << 1, l, mid);
            build(rt << 1 | 1, mid + 1, r);
            node[rt] = node[rt << 1] + node[rt << 1 | 1];
        };
        build(1, 1, n);
    }

    void update(int x, F f) { update(1, 1, n, x, f); }

    T query(int x, int y) { return query(1, 1, n, x, y); }
};

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    SegmentTree<T, F> sgt(32007);
    vector<int> cnt(n);
    for (int i = 1;i <= n;i++) {
        int x, y;
        cin >> x >> y;
        x++, y++;
        cnt[sgt.query(1, x).sum]++;
        sgt.update(x, { 1 });
    }
    for (auto val : cnt) cout << val << '\n';
    return 0;
}

标签:星星,rt,return,int,sum,NC50428,数星星,坐标,Stars
From: https://www.cnblogs.com/BlankYang/p/17360962.html

相关文章