本文主要是介绍HDU 1556 Color the ball (树状数组-- 区间更新,单点求值),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
OJ题目 :点这里~~
与 单点更新,区间求值 稍有不同,需要理解注意。
AC_CODE
int n;
int num[100002];
int lowbit(int x)
{return x&(-x);
}int sum(int x)
{int ret = 0;while(x > 0){ret += num[x];x -= lowbit(x);}return ret;
}void add(int x , int d)
{while(x <= n){num[x] += d;x += lowbit(x);}
}int main()
{while(scanf("%d",&n)&&n != 0){int a , b;memset(num , 0 , sizeof(num));for(int i = 1;i <= n;i++){scanf("%d%d",&a , &b);add(a , 1);//从a开始的加1add(b+1 , -1);//从b+1开始的减1}for(int i = 1;i <= n;i++){i == n ? printf("%d\n",sum(i)) : printf("%d ",sum(i));}}return 0;
}
这篇关于HDU 1556 Color the ball (树状数组-- 区间更新,单点求值)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!