首页 > 代码库 > HDU1556Color the ball【标号法||树状数组】
HDU1556Color the ball【标号法||树状数组】
大意：
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，输入结束。
当N = 0，输入结束。
Output
每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。
分析：
基本思路跟理工门前的树是一样的也就是用标号法就能轻松解决
而sum的值也就是被覆盖了多少次
当然也可以用树状数组求和
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 100005; 7 int num[maxn]; 8 9 int main() {10 int n;11 int a, b;12 while(scanf("%d",&n) && n) {13 memset(num, 0, sizeof(num));14 for(int i = 1; i <= n; i++) {15 scanf("%d %d",&a, &b);16 num[a]++; num[b + 1]--;17 }18 int c = 0;19 int sum = 0;20 for(int i = 1; i <= n; i++) {21 sum += num[i];22 printf(c++?" %d" : "%d", sum);23 }24 puts("");25 }26 return 0;27 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 100005; 7 8 int c[maxn]; 9 10 int lowbit(int x) {11 return x & ( - x );12 }13 14 int n;15 void Add(int i, int num) {16 while(i <= n) {17 c[i] += num;18 i += lowbit(i);19 }20 }21 22 int Sum(int i) {23 int sum = 0;24 while(i > 0) {25 sum += c[i];26 i -= lowbit(i);27 }28 return sum;29 }30 31 int main() {32 int a, b;33 while(scanf("%d",&n) && n) {34 memset(c, 0, sizeof(c));35 for(int i = 1; i <= n; i++) {36 scanf("%d %d",&a, &b);37 Add(a, 1);38 Add(b + 1, -1);39 }40 for(int i = 1; i <= n; i++) {41 printf(i == 1 ? "%d" : " %d", Sum(i));42 }43 puts("");44 }45 return 0;46 }
HDU1556Color the ball【标号法||树状数组】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。