POJ2352：Stars—

Astronomers晚上仰望星空，看到了很多星星。回到办公桌，Astronomers将这些星星画到二维坐标系，每个星星的坐标都是整数。例如5个星星，坐标分别为(1,1), (5,1), (7,1), (3,3), (5,5)：

Astronomers想对这些星星定等级，规则是这样的：每个星星左下角有几个星星，它就算几级（包含左边和下面）。上面的例子，第1颗星星的等级为0，等2颗星星的等级为1，第3颗星星的等级为2，第4颗星星的等级为1，第5颗星星的等级为3。

所以，等级为0的星星有1颗，等级为1的星星有2颗，等级为2的星星有1颗，等级为3的星星有1颗，等级为4的星星为0颗。

给定N个星星坐标，没有两个星星坐标在一起，问你等级为0~N-1的星星数量是多少。

首先对于星星坐标按照先y后x排序，然后按照x的坐标加星星个数统计即可。

****注意星星坐标可能从0开始，所以最开始我们对坐标+1。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

inline ll read(){

    int X=,w=; char ch=;

    while(ch<''||ch>''){w|=ch=='-';ch=getchar();}

    while(ch>=''&&ch<='')X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

const int N=;

struct node{

    int x;

    int y;

}star[];

bool cmp(node a,node b){

    if(a.y<b.y)return ;

    if(a.y>b.y)return ;

    if(a.x<b.x)return ;

    return ;

}

int n,m;

ll tree[N];

ll ans[];

inline int lowbit(int t){return t&(-t);}

void add(int x,int y){

    for(int i=x;i<=N;i+=lowbit(i))tree[i]+=y;

    return;

}

ll query(int x){

    ll res=;

    for(int i=x;i>;i-=lowbit(i))res+=tree[i];

    return res;

}

int main(){

    n=read();

    for(int i=;i<=n;i++){

    star[i].x=read()+;

    star[i].y=read()+;

    }

    sort(star+,star+n+,cmp);

    for(int i=;i<=n;i++){

    int t=query(star[i].x);

    ans[t]++;

    add(star[i].x,);

    }

    for(int i=;i<n;i++){

    printf("%lld\n",ans[i]);

    }

    return ;

}

巴特西

POJ2352：Stars——题解

最新文章

热门文章