题目:https://vjudge.net/problem/POJ-2352

题意:


夜空中有N颗恒星(N≤100000),每颗恒星具有其坐标(x, y)(0≤x, y≤100000)。现在,天文学家要对这些恒星进行分类,分类的标准如下:对于任意一颗恒星S(x,y),如果存在k颗恒星,其x, y坐标均不大于S,则恒星S属于k类星。
如下图所示:第5颗恒星为3类星,这是由1、2、4三颗恒星均在其左下方而得出的,类似地第2、4两颗恒星为1类星,第3颗恒星为2类星。因此在这幅图中只有一颗0类星,共有二颗1类星,2类星和3类星各有一颗。
现给出N颗恒星的坐标,要求统计出0~N-1类星的个数。(翻译摘自博主moep0)

 

解题思路:


对恒星按照x,y排序, 拍完序后已经保证了对于任意的i<j,Xi<Xj,所以只需要对y进行分析

对于一个y值yi,对于任意的i<j且Yj大于等于Yi的恒星来说,对应的k类星的k值要加一,这就相当于update函数

求k类星有多少个相当于getsum函数

 

ac代码:


#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
#define  maxn 100005
#define lowbit(x) ((x)&(-x))
typedef long long ll;
using namespace std;
ll n,a,b,maxy=0,c[maxn]={0},ans[maxn]={0};
struct node{
    ll x,y;
    friend bool operator <(node a,node b)
    {
        return  a.x==b.x?a.y<b.y:a.x<b.x;
    }
}s[maxn];
void update(ll pos)
{
    for(ll i=pos;i<=maxy;i+=lowbit(i))
        c[i]++;
}
ll getsum(ll pos)
{
    ll sum=0;
    for(ll i=pos;i>0;i-=lowbit(i))
        sum+=c[i];
    return sum;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld %lld",&a,&b);
        s[i].x=++a;s[i].y=++b;
        maxy=max(maxy,s[i].y);
    }
    sort(s+1,s+1+n);
    for(ll i=1;i<=n;i++)
    {
        ll k=getsum(s[i].y);
        ans[k]++;
        update(s[i].y);
    }
    for(ll i=0;i<n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}