学步园

Color the ball

Time Limit: 9000/3000 MS
(Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1582    Accepted Submission(s): 1014

Problem Description

N
个气球排成一排，从左到右依次编号为1,2,3....N.
每次给定2
个整数a
b(a <= b),lele
便为骑上他的“
小飞鸽"
牌电动车从气球a
开始到气球b
依次给每个气球涂一次颜色。但是N
次以后lele
已经忘记了第I
个气球已经涂过几次颜
色了，你能帮他算出每个气球被涂过几次颜色吗？

Input

每个测试实例第一行为一个整数N,(N <= 100000).
接下来的N
行，每行包括2
个整数a b(1
<= a <= b <= N)
。

当N = 0
，输入结束。

Output

每个测试实例输出一行，包括N
个整数，第I
个数代表第I
个气球总共被涂色的次数。

Sample Input

3

1 1

2 2

3 3

3

1 1

1 2

1 3

0

Sample Output

1 1 1

3 2 1

简单线段树
,
入门练习题
.

代码如下
:

#include<stdio.h><br /> #include<string.h><br /> #define MAXN 100005<br /> struct ST<br /> {<br /> int l,r,sum;<br /> }st[MAXN*3];<br /> int nn;<br /> void build(int ll,int rr,int n)<br /> {<br /> st[n].l=ll;<br /> st[n].r=rr;<br /> st[n].sum=0;<br /> if (ll==rr) return ;<br /> int mid=(ll+rr)/2;<br /> build(ll,mid,2*n);<br /> build(mid+1,rr,2*n+1);<br /> };<br /> void color(int ll,int rr,int n)<br /> {<br /> if (st[n].l==ll&&st[n].r==rr) {st[n].sum++;return ;}<br /> int mid=(st[n].l+st[n].r)/2;<br /> if (rr<=mid) color(ll,rr,2*n);<br /> else<br /> if (ll>=mid+1) color(ll,rr,2*n+1);<br /> else<br /> {<br /> color(ll,mid,2*n);<br /> color(mid+1,rr,2*n+1);<br /> }<br /> }<br /> void out(int n,int sum)<br /> {<br /> if (st[n].l==st[n].r) {printf("%d",sum+st[n].sum);if (st[n].l!=nn) printf(" ");return;}<br /> out(2*n,sum+st[n].sum);<br /> out(2*n+1,sum+st[n].sum);<br /> }<br /> int main()<br /> {<br /> int i,p,q;<br /> while (scanf("%d",&nn)&&nn)<br /> {<br /> build(1,nn,1);<br /> for (i=1;i<=nn;++i)<br /> {<br /> scanf("%d%d",&p,&q);<br /> color(p,q,1);<br /> }<br /> out(1,0);<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />