首页 > 代码库 > hdu 1556 Color the ball
hdu 1556 Color the ball
可以使用线段树来做，但是使用树状数组会更加简洁，对于第i个点被涂的次数$s$，为$s=\sum_{k=1}^{i}x_k$，因此对于区间$[a,b]$的涂色，对于下标$a$增加一，对于下标$b+1$减少一，这样就可以保证对于$i\in [a,b]$中的点，$s$加一，对于$i \notin [a,b]$的点$s$ 不变。
代码如下：
1 #define MAX_N 1000007 2 #include <cstdlib> 3 #include <cstdio> 4 #include <iostream> 5 #include <cstring> 6 using namespace std; 7 int bit[MAX_N+1], n; 8 int lowbit(int x) 9 {10 return x&(-x);11 }12 int sum(int i)13 {14 int s = 0;15 while( i > 0 )16 {17 s += bit[i];18 i -= lowbit(i);19 }20 return s;21 }22 void add(int i , int x)23 {24 while( i <= n )25 {26 bit[i] += x;27 i += lowbit(i);28 }29 }30 int main()31 {32 int a,b;33 while(scanf("%d",&n),n)34 {35 memset(bit,0,sizeof(bit));36 for(int i=0;i<n;i++)37 {38 scanf("%d%d",&a,&b);39 add(a,1);40 add(b+1,-1);41 }42 for(int i=1;i<n;i++)43 printf("%d ",sum(i));44 printf("%d\n",sum(n));45 }46 return 0;47 }
hdu 1556 Color the ball
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。