hdu 1556 Color the ball 树状数组

缘起

【1】是本题的二维版本 hdu 1556 Color the ball

即【1】是二维树状数组, 而本题是一维数组数组.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞
鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次
颜色了，你能帮他算出每个气球被涂过几次颜色吗？

【输入】
每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。

【输出】
每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

【样例输入】
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

【样例输出】
1 1 1
3 2 1

【限制】
3s

树状数组水题~ 将[a,b]涂色拆成从[a,n]涂色次数+1和[b,n]涂色次数-1即可. 本题比较恶心的是输入而已.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int maxn = 1e5+5;
int n, c[maxn],a[2];
char s[105];
inline int lowbit(int i)
{
	return i&-i;
}

void updata(int i, int d)
{
	while(i<=n)
	{
		c[i]+=d;
		i+=lowbit(i);
	}
}

int query(int i)
{
	int ans = 0;
	while(i)
	{
		ans+=c[i];
		i-=lowbit(i);
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(1)
	{
		a[0] = a[1] = 0;
		gets(s);
		sscanf(s,"%d%d",a,a+1);
		if (!a[1]) // 如果该行仅仅有一个数, 表示一个新的样例的开始,则要做的事情是打印上一个测试用例的答案, 并且清空树状数组,为新的样例计算做准备
		{
			if (kase)
			{
				for (int i = 1;i<=n;i++)
				{
					printf("%d",query(i));
					if (i<n)
					{
						putchar(' ');
					}
				}
				puts("");
			}
			n = a[0];
			if (!n)
			{
				break;
			}
			memset(c,0,sizeof(c));
			++kase;
		}
		else
		{
			updata(a[0], 1);
			updata(a[1]+1, -1);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 499ms
Memory 1608kB
Length 941
Lang G++
Submitted 2019-10-22 13:31:59
Shared
RemoteRunId 31038962

参考

【1】https://yfsyfs.github.io/2019/10/21/poj-2155-Matrix-%E4%BA%8C%E7%BB%B4%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/