---

題目描述

夜空中有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類星的個數。

---

輸入格式

輸入文件第一行包含一個整數N，表示恒星總數。
接下來的N行每行兩個整數表示一顆恒星的坐標。不存在兩顆星擁有相同的坐標。

---

輸出格式

輸出文件包含N行，每行包含一個整數，第i行表示第i-1類星的數量。

---

樣例數據

樣例輸入

5
3 3
5 1
5 5
1 1
7 1

樣例輸出

1
2
1
1
0

---

數據范圍

對于20%的數據，n<=1000；
對于100%的數據， n<=100000；

---

題目分析

要統計左下方的點數
二維不好統計，先按照x從小到大排序，因此就只用統計下方的點數了。
可以使用樹狀數組輕松解決。
樹狀數組維護y坐標，插入后查詢比他小的求和即可

---

源代碼

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> #include<map> using namespace std; map<int,int>M,M2; map<int,int>::iterator it; int n,m,f[500005],ans[500005]; struct node {int x,y; } a[500005]; const int Get_Int() {int n=0,bj=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')bj=-1;x=getchar();}while(x>='0'&&x<='9'){n=n*10+x-'0';x=getchar();}return n*bj; } int Lowbit(int x) {return x&-x; } void Add(int x,int d) {for(int i=x; i<=m; i+=Lowbit(i))f[i]+=d; } int Ask(int r) {int sum=0;for(int i=r; i>=1; i-=Lowbit(i))sum+=f[i];return sum; } bool cmp(node x,node y) {if(x.x==y.x)return x.y<=y.y;return x.x<y.x; } int main() {n=Get_Int();for(int i=1; i<=n; i++) {a[i].x=Get_Int()+1;a[i].y=Get_Int()+1;m=max(m,a[i].y);}sort(a+1,a+n+1,cmp);for(int i=1; i<=n; i++) {ans[Ask(a[i].y)]++;Add(a[i].y,1);}for(int i=0; i<n; i++)printf("%d\n",ans[i]);return 0; }

---

總結

以上是生活随笔為你收集整理的[POJ2352] Stars 夜空星辰 - 树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。