HDU 1556 Color the ball （树状数组简单应用）

HDU 1556 Color the ball （树状数组简单应用）

【题目链接】：​​click here~~​​

【题目大意】：

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

【思路】：本题是树状数组的应用，初始建树状数组时的add（x,d），因为是刷一遍，只需加一即可，为使前面的数消除影响，add（a-1,-1）处理之后，树状数组的各点sum值，就表示每个气球被刷的次数。详见代码吧

代码：

#include using namespace std;const int N=100005;int t,bit[N];int lowbit(int x){return x&(-x);}void add(int i,int n){ while(i>0){ bit[i]+=n; i-=lowbit(i); }}int sum(int i){ int s=0; while(i<=N){ s+=bit[i]; i+=lowbit(i); } return s;}int main(){ while(~scanf("%d",&t)&&t!=0){ int a,b; memset(bit,0,sizeof(bit)); for(int i=0; i

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