POJ 2352 Stars[树状数组]

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

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

代码

代码语言：javascript复制

#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;
}

int return 排序 数组 统计

0 人点赞