HDU 1556 Color the ball(ツリー配列区間更新)
3946 ワード
水題では,樹状配列の区間更新を練習する.
各区間について,区間左端点+1,右端点の下位ビット−1について,各位置の上書き回数を問い合わせる.
各区間について,区間左端点+1,右端点の下位ビット−1について,各位置の上書き回数を問い合わせる.
#include <cstdio>
#include <cstring>
const int MAXN = 100005;
int N, C[MAXN];
int lowbit( int x )
{
return (-x)&x;
}
void update(int x, int add)
{
for(int i = x; i <= N; i += lowbit(i))
C[i] += add;
return;
}
int sum(int x)
{
int ret = 0;
for(int i = x; i > 0; i -= lowbit(i))
ret += C[i];
return ret;
}
int main()
{
while( scanf("%d", &N)== 1 && N )
{
memset(C, 0, sizeof(C));
for(int i = 1; i <= N; i++)
{
int a, b;
scanf("%d%d",&a,&b);
update(a, 1);
update(b + 1, -1);
}
for(int i = 1; i <= N; i++)
{
if ( i > 1 ) putchar(' ');
printf( "%d", sum(i) );
}
puts("");
}
return 0;
}