hdu1556 Color the ball

Problem Description

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

简单的区间修改，单点统计。

1、离散化 ； 2、树状数组； 3、线段树

1、离散化

#include 
  
   
#include 
   
     #define MAXN 100000 + 5 int bit[MAXN]; int main() { int n, i, a, b; while(scanf("%d",&n), n ) { memset(bit, 0, sizeof bit ); for(i=0; i
     
     

 





 
     

 
 
     
2、树状数组
 
     

     
#include 
      
       
#include 
       
         #define MAXN 100000 + 5 int c[MAXN], n; int lowbit(int x) {return (x&-x);} void update(int i, int d) { for(;i<=n; i+=lowbit(i)) c[i]+=d; } int getsum(int i) { int ret=0; for(;i>0; i-=lowbit(i)) ret+=c[i]; return ret;} int main() { int i, a, b; while(scanf("%d",&n),n) { memset(c, 0, sizeof c ); for(i=0; i
        
         
 
         
 
         
3、线段树