線分の木の水題----今日はまず初心者の基礎を書きます

hdu 1556から直接問題を話せます

     
using namespace std;
#define MAXN 100005
struct ST
{
    int l,r,sum;  //       l，r    ，sum           
}st[MAXN*3];
int nn;
void build(int L,int R,int n)    //     ，      ，         。
{
    st[n].l=L;
    st[n].r=R;
    st[n].sum=0;
    if (L==R) return ;
    int mid=(L+R)/2;
    build(L,mid,2*n);
    build(mid+1,R,2*n+1);
};
void color(int L,int R,int n){  //  :    ，st[n] [l,r]  ，           
                                 //[l,r]           st[n].sum 
    if (st[n].l==L&&st[n].r==R) {st[n].sum++;return ;}
    int mid=(st[n].l+st[n].r)/2;
    if (R<=mid) color(L,R,2*n);
    else
    if (L>=mid+1) color(L,R,2*n+1);
    else                         //   L,R  mid    ，       [L,mid] [mid+1,R]   
    {
        color(L,mid,2*n);
        color(mid+1,R,2*n+1);
    }
}
void out(int n,int sum)          //    ，      ，                       
{
    if (st[n].l==st[n].r) {printf("%d",sum+st[n].sum);if (st[n].l!=nn) printf(" ");return;}
    out(2*n,sum+st[n].sum);
    out(2*n+1,sum+st[n].sum);
}
int main()
{
    //freopen("1.txt","r",stdin);
    int i,p,q;
    while (scanf("%d",&nn)&&nn)
    {
        build(1,nn,1);        //   
        for (i=1;i<=nn;++i) 
        {
            scanf("%d%d",&p,&q);
            color(p,q,1);   
        }
        out(1,0);
        printf("
");
    }
    return 0;
}