poj 2352_Stars_树状数组

发布于 2019-05-23  12 次阅读


题目大意

定义星星的等级为在它左下角(包括正左和正下)的星星的个数。
给出若干个星星的坐标(不超过15000个),输出各个等级的星星分别有多少个。
每个星星的坐标不超过32000,输入时按照Y坐标升序输入。


思路

因为坐标有可能是0,所以读入是将全部数加一,然后因为按y轴排好了序,所以用树状数组记录x轴坐标到0之间有几个就可以了


#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define maxn 50001
struct arr
{
    int x, y;
}a[maxn];
int n, t[maxn], ans[maxn];
int count(int p)
{
    int an = 0;
    while (p > 0)
    {
        an += t[p];
        p -= p & (-p);
    }
    return an;
}
int add(int p, int x)
{
    while (p <= 32005)
    {
        t[p] += x;
        p += p & (-p);
    }
    return 0;
}
int main()
{
    while(~scanf("%d", &n))
    {
        fill(ans, 0);
        fill(t, 0);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &a[i].x, &a[i].y);
            a[i].x++; a[i].y++;
            ans[count(a[i].x)]++;
            add(a[i].x, 1);
        }
        for (int i = 0; i < n; i++)
            printf("%d\n", ans[i]);
    }
}
]]>