1. #include?<stdio.h>??
2. #include?<conio.h>??
3. #include?<string.h>??
4. ??
5. #define?max(x1,?y1)?((x1)?>?(y1)???(x1)?:?(y1))??
6. #define?min(x1,?y1)?((x1)?<?(y1)???(x1)?:?(y1))??
7. ??
8. #define?MAXSIZE?200002??
9. ??
10. typedef?struct?{??
11. ????int?max?;??
12. ????int?left,?right?;??
13. }?NODE?;??
14. ??
15. int?????n,?m?;??
16. int?????num?[MAXSIZE]?;??
17. NODE????tree[MAXSIZE?*?20]?;??
18. ??
19. //?構建線段樹??
20. int?build?(int?root,?int?left,?int?right)??
21. {??
22. ????int?mid?;??
23. ??
24. ????//?當前節點所表示的區間??
25. ????tree[root].left?????=?left?;??
26. ????tree[root].right????=?right?;??
27. ??
28. ????//?左右區間相同，則此節點為葉子，max?應儲存對應某個學生的值??
29. ????if?(left?==?right)??
30. ????{??
31. ????????return?tree[root].max?=?num[left]?;??
32. ????}??
33. ????mid?=?(left?+?right)?/?2?;??
34. ??
35. ????//?遞歸建立左右子樹，并從子樹中獲得最大值??
36. ????int?a,?b?;??
37. ????a?=?build?(2?*?root,?left,?mid)?;??
38. ????b?=?build?(2?*?root?+?1,?mid?+?1,?right)?;??
39. ??
40. ????return?tree[root].max?=?max?(a,?b)?;??
41. }??
42. ??
43. //?從節點?root?開始，查找?left?和?right?之間的最大值??
44. int?find?(int?root,?int?left,?int?right)??
45. {??
46. ????int?mid?;??
47. ????//?若此區間與?root?所管理的區間無交集??
48. ????if?(tree[root].left?>?right?||?tree[root].right?<?left)??
49. ????????return?0?;??
50. ????//?若此區間包含?root?所管理的區間??
51. ????if?(left?<=?tree[root].left?&&?tree[root].right?<=?right)??
52. ????????return?tree[root].max?;??
53. ??
54. ????//?若此區間與?root?所管理的區間部分相交??
55. ??
56. ????int?a,?b?;??//?不能這樣?max?(find(...),?find(...));??
57. ????a?=?find?(2?*?root,?left,?right)?;??
58. ????b?=?find?(2?*?root?+?1,?left,?right)?;??
59. ??
60. ????return?max?(a,?b)?;??
61. }??
62. ??
63. //?更新?pos?點的值??
64. int?update?(int?root,?int?pos,?int?val)??
65. {??
66. ????//?若?pos?不存在于?root?所管理的區間內??
67. ????if?(pos?<?tree[root].left?||?tree[root].right?<?pos)??
68. ????????return?tree[root].max?;??
69. ??
70. ????//?若?root?正好是一個符合條件的葉子??
71. ????if?(tree[root].left?==?pos?&&?tree[root].right?==?pos)??
72. ????????return?tree[root].max?=?val?;??
73. ??
74. ????//?否則。。。。??
75. ??
76. ????int?a,?b?;??//?不能這樣?max?(find(...),?find(...));??
77. ????a?=?update?(2?*?root,?pos,?val)?;??
78. ????b?=?update?(2?*?root?+?1,?pos,?val)?;??
79. ??
80. ????tree[root].max?=?max?(a,?b)?;??
81. ??
82. ????return?tree[root].max?;??
83. }??
84. ??
85. int?main?()??
86. {??
87. ????char?c?;??
88. ????int?i?;??
89. ????int?x,?y?;??
90. ????while?(scanf?("%d%d",?&n,?&m)?!=?EOF)??
91. ????{??
92. ????????for?(i?=?1?;?i?<=?n?;?++i)??
93. ????????????scanf?("%d",?&num[i])?;??
94. ????????build?(1,?1,?n)?;??
95. ??
96. ????????for?(i?=?1?;?i?<=?m?;?++i)??
97. ????????{??
98. ????????????getchar?()?;??
99. ????????????scanf?("%c%d%d",?&c,?&x,?&y)?;??
100. ????????????if?(c?==?'Q')??
101. ????????????{??
102. ????????????????printf?("%d\n",?find?(1,?x,?y))?;??
103. ????????????}??
104. ????????????else??
105. ????????????{??
106. ????????????????num[x]?=?y?;??
107. ????????????????update?(1,?x,?y)?;??
108. ????????????}??
109. ????????}??
110. ????}??
111. ????return?0?;??
112. } ?

總結

以上是生活随笔為你收集整理的hdu1754的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。