HDU 1556 Color the ball

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=100005;
 4 int tree[MAXN];
 5 int n;
 6 void add(int k,int num)//后面的所有的值得更新，不包括自身
 7 {
 8     while(k<=n)
 9     {
10         tree[k]+=num;// 增加某个元素的大小
11         k+=k&-k;
12     }
13 }
14 int read(int k)
15 {
16     int sum=0;
17     while(k)
18     {
19         sum+=tree[k];//统计k以前的总数，即求该点的染色次数
20         k-=k&-k;
21     }
22     return sum;
23 }
24 int main()
25 {
26     int x,y,i;
27     while(scanf("%d",&n)&&n)
28     {
29         memset(tree,0,sizeof(tree));
30         for(i=0;i<n;i++)
31         {
32             scanf("%d%d",&x,&y);
33             add(x,1);//插线段的话就在线段左端点加1
34             add(y+1,-1);//在右端点后面减1
35         }
36         for(i=1;i<n;i++)
37             printf("%d ",read(i));
38         printf("%d\n",read(n));
39     }
40     return 0;
41 }