hdu 1556Color the ball

本文主要是介绍hdu 1556Color the ball，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                               这个题是更新区间，查询点；是简单的线段树和树状数组的应用；不过线段树再简单应用上， 不用做任何变化及可以直接套用， 而树状数组却不同， 它在处理1:更新点,查询区间 2：更新区间，查询点 。这两种基本类型时，需要变化一下;

#include<stdio.h>
#include<string.h>
int n, c[100001];void update(int i, int data) 
{while(i<=n){c[i]+=data;i+=i&(-i);	}
}int query(int i)
{int sum=0;while(i>0){sum+=c[i];i-=i&(-i);}return sum;
}
int main()
{int a, b;while( scanf("%d", &n) && n ){memset(c,0,sizeof(c));for(int i=1; i<=n; i++){scanf("%d %d",&a, &b);//给[a,b]染色,  update(a, 1);//a以后的每个球都染色一次（包含a）；update(b+1, -1);//b以后的每个气球染色次数都减少1}for(int i=1; i<n; i++)printf("%d ", query(i));printf("%d\n", query(n));}
}

下边有一种更巧的方法， 纯数组过的……很好很强大……

#include<stdio.h>
#include<string.h>
int main()
{int  n, c[100002], a, b, sum;while( scanf("%d", &n) && n ){memset(c,0,sizeof(c));for(int i=1; i<=n; i++){scanf("%d %d",&a, &b);//给[a,b]染色,  c[a]++;c[b+1]--;}sum=c[1];printf("%d", sum);for(int i=2; i<=n; i++){sum+=c[i];printf(" %d", sum);}printf("\n");}
}

这篇关于hdu 1556Color the ball的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---