又一道树状数组的题。注意坐标值有可能为0，会导致死循环，都加1就可以了。
1 #include <iostream>
2 using namespace std;
3 int n;
4 int star[15011][2];
5 int num[15011];
6 int t[40011];
7 int ans[15011];
8
9 int lowbit(int x){
10 return x&(-x);
11 }
12
13 int sum(int x){
14 int re=0;
15 while (x>0){
16 re+=t[x];
17 x-=lowbit(x);
18 }
19 return re;
20 }
21 void insert(int x){
22 while (x<=32011){
23 ++t[x];
24 x+=lowbit(x);
25 }
26 }
27
28 int main(){
29 srand(102323);
30 scanf("%d",&n);
31 for (int i=1;i<=n;++i) scanf("%d %d",&star[i][0],&star[i][1]);
32 for (int i=1;i<=n;++i){
33 num[i]=sum(star[i][0]+1);
34 insert(star[i][0]+1);
35 }
36 for (int i=1;i<=n;++i) ++ans[num[i]];
37 for (int i=0;i<n;++i) printf("%d\n",ans[i]);
38 }
39
posted on 2008-11-10 20:38
Joseph 阅读(295)
评论(0) 编辑 收藏 引用