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): 28415 Accepted Submission(s): 13851
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28415 Accepted Submission(s): 13851
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
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 MAX = 5e5 + 10; 14 15 int n, a, b; 16 17 struct nod 18 { 19 int L, R, val; 20 }node[MAX]; 21 22 void build(int d, int l, int r) 23 { 24 node[d].L = l, node[d].R = r, node[d].val = 0; 25 if (l == r) return; 26 int mid = (l + r) >> 1; 27 build(d << 1, l, mid); 28 build((d << 1) + 1, mid + 1, r); 29 } 30 31 void update(int d, int l, int r) 32 { 33 if (node[d].L == l && node[d].R == r) 34 { 35 node[d].val ++; 36 return; 37 } 38 if (node[d].L == node[d].R) return; 39 int mid = (node[d].L + node[d].R) >> 1; 40 if (r <= mid) 41 update(d << 1, l, r); 42 else if (mid < l) 43 update((d << 1) + 1, l, r); 44 else 45 { 46 update(d << 1, l, mid); 47 update((d << 1) + 1, mid + 1, r); 48 } 49 } 50 51 int query(int d, int l, int r) 52 { 53 if (node[d].L == l && node[d].R == r) return node[d].val; 54 if (node[d].L == node[d].R) return 0; 55 int mid = (node[d].L + node[d].R) >> 1; 56 if (r <= mid) 57 return node[d].val + query(d << 1, l, r); 58 else if (mid < l) 59 return node[d].val + query((d << 1) + 1, l, r); 60 else 61 return node[d].val + query(d << 1, l, mid) + query((d << 1) + 1, mid + 1, r); 62 } 63 64 int main() 65 { 66 while (scanf("%d", &n), n) 67 { 68 build(1, 1, n); 69 for (int i = 0; i < n; ++ i) 70 { 71 scanf("%d%d", &a, &b); 72 update(1, a, b); 73 } 74 for (int i = 1; i < n; ++ i) 75 printf("%d ", query(1, i, i)); 76 printf("%d\n", query(1, n, n)); 77 } 78 return 0; 79 }
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 MAX = 1e5 + 10; 14 15 int n, a, b; 16 17 int main() 18 { 19 while (scanf("%d", &n), n) 20 { 21 int num[MAX] = {0}, m = 0; 22 for (int i = 1; i <= n; ++ i) 23 { 24 scanf("%d%d", &a, &b); 25 num[a] ++, num[b + 1] --; 26 } 27 for (int i = 1; i < n; ++ i) 28 { 29 m += num[i]; 30 printf("%d ", m); 31 } 32 printf("%d\n", m + num[n]); 33 } 34 return 0; 35 }
相关文章
- MacOS安装Eclipse后启动报错:The JVM shared library "/Library/Internet Plug-Ins/JavaAppletPlugin.plugin/Contents/Home/bin/../lib/server/libjvm.dylib" does not contain the JNI_CreateJavaVM symbol.
- 【异常】[ERROR] The cloud assistant is not installed on the ECS, or the cloud assistant is unavailable. cloudassistant is uninstall
- [zsh]zsh常用小技巧
- The total number of locks exceeds the lock table size错误(已纠正)
- sharepoint2010:The number of items in this list exceeds the list view threshold, which is 20000 items.
- [RxJS 6] The Catch and Rethrow RxJs Error Handling Strategy and the finalize Operator
- Excel:python结合Excel使用技巧经验总结之(将python输出的等间隔列数据直接粘贴复制存到物理表格内等)图文教程之详细攻略
- NLP:LSTM之父眼中的深度学习十年简史《The 2010s: Our Decade of Deep Learning / Outlook on the 2020s》的参考文献
- 成功解决The following specifications were found to be incompatible with the existing python installation
- Android ViewPager 应该及技巧
- Caused by: org.xml.sax.SAXParseException; systemId: file:/home/hadoop/hive-0.12.0/conf/hive-site.xml; lineNumber: 5; columnNumber: 2; The markup in the document following the root element must be well
- Java-小技巧-006 List 排序 Collections.sort()
- 【问题解决】The connection to the server localhost:8080 was refused
- 问题解决:The connection to the server xxxxx:6443 was refused - did you specify the right host or port?
- C语言使用技巧(八):与众不同地计算数组元素出现的次数和元素所在位置的索引号
- 用conda安装包出现The environment is inconsistent, please check the package plan carefully
- DB2 “The transaction log for the database is full” 存在的问题及解决方案
- (a*b)%c 小的技巧
- 【SQL开发实战技巧】系列(十二):三问(如何对字符串字母去重后按字母顺序排列字符串?如何识别哪些字符串中包含数字?如何将分隔数据转换为多值IN列表?)
- 解决办法:The name 'Response' does not exist in the current context
- 如何使用GOOGLE高级搜索技巧
- The value for the useBean class attribute is invalid.
- ERROR 1290 (HY000): The MySQL server is running with the --secure-file-priv option so it cannot ···
- Sentinel采用SphO方式定义资源,报错:The order of entry exit can‘t be paired with the order of entry
- Accidental override: The following declarations have the same JVM signature (getWindow()Landroid/vie