数

星

星

S

t

a

r

s

数星星 Stars

数星星Stars

题目描述

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下）有

k

k

k 颗星星，就说这颗星星是

k

k

k级的。

给定星星的位置，输出各级星星的数目。

一句话题意：给定

n

n

n个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入

第一行一个整数

N

N

N，表示星星的数目；

接下来

N

N

N行给出每颗星星的坐标，坐标用两个整数

x

,

y

x,y

x,y表示；

不会有星星重叠。星星按

y

y

y坐标增序给出，

y

y

y坐标相同的按

x

x

x 坐标增序给出。

输出

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

样例输入

5

1 1

5 1

7 1

3 3

5 5

样例输出

1

2

1

1

0

数据范围与提示：

对于全部数据，1≤N≤1.5×104 ,0≤x,y≤3.2×104。

题目解析

我刚看到题目的时候以为是用线段树维护的暴力，但看了看数据，会爆；于是就用树状数组 树状数组的初步了解 详解树状数组以下是树状数组的代码

code

#include<stdio.h>#include<iostream>usingnamespace std;int n,x,y,s,a[32005],b[32005];int cx(int x){ s=0;for(;x;x-=x&(-x))s+=a[x];return s;}void add(int x,int y){for(;x<=32001;x+=x&(-x))a[x]+=y;}int main(){ scanf(“%d”,&n);for(int i=1;i<=n;i++){ scanf(“%d%d”,&x,&y); b[cx(x+1)]++; add(x+1,1);}for(int i=1;i<=n;i++) printf(“%d\n”,b[i–1]);return0;}