数星星 Stars

问题 A: 数星星 Stars

时间限制: 1 Sec 内存限制: 128 MB
[命题人:admin]

题目描述

输入

第一行一个整数 N，表示星星的数目；
接下来 N 行给出每颗星星的坐标，坐标用两个整数 x,y 表示；
不会有星星重叠。星星按 y 坐标增序给出， y坐标相同的按 x 坐标增序给出。

输出

N 行，每行一个整数，分别是 0 级，1 级，2 级，……，N-1 级的星星的数目。

样例输入 Copy

样例输出 Copy

提示

对于全部数据，1<=N<=1.5*10⁴, 0<=x,y<=3.2*10⁴。

每一颗星星需要统计它的左下方的星星个数。

我们发现题目是按照纵坐标从小到大输入的，对于相同的纵坐标是按照横坐标从小到大输入。

也就是说，我们可以不管纵坐标，按照它给出的横坐标依次插入，并统计当前星星之前的横坐标小于它的星星个数

AC代码：

#include<cstring>

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

inline ll read()

{

    int x=,f=;char ch=getchar();

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

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=1e6+;

ll c[maxn];

ll ans[maxn];

ll n;

ll lowbit(ll x){

    return x&(-x);

}

void updata(ll i,ll k){    //在i位置加上k

    while(i <= ){

        c[i] += k;

        i += lowbit(i);

    }

}

ll getsum(ll i){        //求A[1 - i]的和(适合于只变化点的树状数组求区间和）

    ll res = ;

    while(i > ){

        res += c[i];

        i -= lowbit(i);

    }

    return res;

}

struct node{

    ll x,y;

}a[maxn];

int main(){

    n=read();

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

        a[i].x=read();

        a[i].y=read();

    }

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

        int xx=a[i].x+;

        int t=getsum(xx);

        updata(xx,);

        ans[t]++;

    }

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

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

    }

    return ;

}

巴特西

数星星 Stars

问题 A: 数星星 Stars

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

提示

最新文章

热门文章