POJ 2352 Stars[树状数组]

算法

字数统计: 262阅读时长: 1 min

 2019/01/02   Share

原题链接
题目大意
给出一些星星的二维坐标，求星星左方，下方，左下方的星星个数。

思路
题目已经把星星按照 y 坐标从小到大排序，若 y 相等则按 x 从小到大排序。因此，在每次对一个星星进行统计时，之前出现过的星星，只要 x 坐标比其小，则必在其左，左下方，x 坐标相等的自然在下方。

代码

#include <iostream>
using namespace std;

const int N = 4e4;  // 注意此处
int arr[N] = {0};
int ans[N/2] = {0}, n;

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

void add(int i, int v) {
    while(i < N) {  // 注意是 N
        arr[i] += v;
        i += lowbit(i);
    }
}

int Sum(int x) {
    int res = 0;
    while(x) {
        res += arr[x];
        x -= lowbit(x);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 0; i < n; i++) {
        int x, y; cin>>x>>y;
        ans[Sum(++x)]++;  // x 要加一
        add(x, 1);
    }
    for(int i = 0; i < n; i++)
        cout<<ans[i]<<endl;

    return 0;
}

原文作者：wywwzjj

原文链接：https://wywwzjj.top/2019/01/02/POJ-2352-Stars-树状数组/

发表日期：January 2nd 2019, 9:52:33 am

更新日期：May 15th 2021, 11:53:20 am

Next Post

2019 fireshell web Vice
Previous Post

POJ 2352 Stars[树状数组]

CATALOG

