hdu 1556 Color the ball

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100100
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int l,r;
10     int flag;
11 }tree[maxn*4];
12 int ans=0;
13 
14 void build(int i,int l,int r)
15 {
16     tree[i].l=l;tree[i].r=r;
17     tree[i].flag=0;
18     if(l==r) return ;
19     int mid=(l+r)>>1;
20     build(i<<1,l,mid);
21     build(i<<1|1,mid+1,r);
22 }
23 
24 void insert1(int i,int l,int r)
25 {
26     if(tree[i].l==l&&tree[i].r==r)
27     {
28         tree[i].flag++;
29         return ;
30     }
31     int mid=(tree[i].l+tree[i].r)>>1;
32     if(r<=mid)
33     {
34         insert1(i<<1,l,r);
35     }
36     else if(l>mid)
37     {
38         insert1(i<<1|1,l,r);
39     }
40     else
41     {
42         insert1(i<<1,l,mid);
43         insert1(i<<1|1,mid+1,r);
44     }
45 }
46 
47 void search1(int x,int i)
48 {
49     ans+=tree[i].flag;
50     if(tree[i].l==tree[i].r) return ;
51     int mid=(tree[i].l+tree[i].r)>>1;
52     if(x<=mid)
53     {
54         search1(x,i<<1);
55     }
56     else
57         search1(x,i<<1|1);
58 }
59 
60 int main()
61 {
62    int n;
63    while(scanf("%d",&n)!=EOF)
64    {
65        if(n==0) break;
66        int a,b;
67        build(1,1,n);
68        for(int i=0; i<n; i++)
69        {
70            scanf("%d%d",&a,&b);
71            insert1(1,a,b);
72        }
73        for(int i=1; i<=n; i++)
74        {
75            ans=0;
76            if(i==1)
77            {
78                search1(1,1);
79                printf("%d",ans);
80            }
81            else
82            {
83                search1(i,1);
84                printf(" %d",ans);
85            }
86        }
87        printf("\n");
88    }
89    return 0;
90 }