hdu 1556 Color the ball (树状数组)
数组 The HDU 树状 Color
2023-09-11 14:21:10 时间
Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28423 Accepted Submission(s): 13858
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28423 Accepted Submission(s): 13858
Problem Description
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,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0,输入结束。
Output
每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。
每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
1 1 1
3 2 1
引至:help
C/C++:
1 #include <map> 2 #include <queue> 3 #include <cmath> 4 #include <vector> 5 #include <string> 6 #include <cstdio> 7 #include <cstring> 8 #include <climits> 9 #include <iostream> 10 #include <algorithm> 11 #define INF 0x3f3f3f3f 12 using namespace std; 13 const int MAXN = 1e5 + 10; 14 int n, c[MAXN], a, b; 15 16 int lowbit(int x) 17 { 18 return x & (-x); 19 } 20 21 void add(int x, int val) 22 { 23 while (x <= n) 24 { 25 c[x] += val; 26 x += lowbit(x); 27 } 28 } 29 30 int sum(int x) 31 { 32 int sum = 0; 33 while (x >= 1) 34 { 35 sum += c[x]; 36 x -= lowbit(x); 37 } 38 return sum; 39 } 40 41 int main() 42 { 43 while (scanf("%d", &n), n) 44 { 45 memset(c, 0, sizeof(c)); 46 for (int i = 1; i <= n; ++ i) 47 { 48 scanf("%d%d", &a, &b); 49 add(a, 1); 50 add(b + 1, -1); 51 } 52 for (int i = 1; i < n; ++ i) 53 printf("%d ", sum(i)); 54 printf("%d\n", sum(n)); 55 } 56 }
相关文章
- PAT 乙级 -- 1008 -- 数组元素循环右移问题
- C语言动态二位数组雏形
- BZOJ1991 : Pku2422 The Wolves and the Sheep
- The platform of the target `Pods` (iOS 4.3) is not compatible 错误
- ERROR ITMS-90717: “Invalid App Store Icon. The App Store Icon in the asset catalog in ‘HBuilder.app‘
- java中byte数组与int类型的转换(两种方式)
- C#实现字符串按多个字符采用Split方法分割得到数组
- 学习笔记——Linux写入整型、结构体数组到文件
- SPOJ CIRU The area of the union of circles (计算几何)
- Java数组
- .NET删除字节数组中的0字节
- Perl数组和hash相关函数
- ubuntu添加源报错The following signatures couldn't be verified because the public key is not available
- 《交互式程序设计 第2版》一2.3.2 数组
- Mysql_解决The total number of locks exceeds the lock table size错误
- 快速排序,归并排序,堆排序的数组和单链表实现
- 微信小程序 数组更新问题
- 求连续子数组的最大乘积
- [LeetCode] 523. Continuous Subarray Sum 连续的子数组之和
- The model backing the context has changed since the database was created.
- Eclipse中使用MySql遇到:Loading class `com.mysql.jdbc.Driver'. This is deprecated. The new driver class is `com.mysql.cj.jdbc.Driver'. The driver is automatically registered via the SPI and manual loading o
- 全局变量和局部变量对于数组大小的问题
- List数组转换JSON格式