hdu1556 Color the ball(线段树区间更新)

hdu1556 Color the ball(线段树区间更新)

Color the ball

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

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

Author

8600

Source

​​HDU 2006-12 Programming Contest​​

Recommend

LL   |   We have carefully selected several similar problems for you:   ​​1166​​​  ​​​1542​​​  ​​​1394​​​  ​​​1698​​​  ​​​1255​​

​​Statistic​​ |

​​Submit​​ |

​​Discuss​​ |

​​Note​​

一个线段树区间更新问题。。直接写就是了

每次更新为了节省时间只需在需要更新的区间+1就OK了。

#include #include struct node{ int left,right,count;}c[100005*3];int sum[100005];void build(int l,int r,int root)//这个就不多说了{ c[root].left=l; c[root].right=r; c[root].count=0; if(l==r) return ; int mid=(l+r)/2; build(l,mid,root*2); build(mid+1,r,root*2+1);}void update(int l,int r,int root)//更新{ if(c[root].left==l&&c[root].right==r)//只需要在这个区间+1就行了，节省时间，不用找到每个数 { c[root].count++; return ; } int mid=(c[root].left+c[root].right)/2; if(mid=r) update(l,r,root*2); else { update(l,mid,root*2); update(mid+1,r,root*2+1); }}void tosum(int root)//求和{ for(int i=c[root].left;i<=c[root].right;i++) sum[i]+=c[root].count; if(c[root].left==c[root].right) return ; tosum(root*2); tosum(root*2+1);}int main(){ int n; while(scanf("%d",&n)&&n) { memset(sum,0,sizeof(sum)); memset(&c,0,sizeof(&c)); build(1,n,1); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。