HDU 1754 I Hate It(线段树）

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 89455 Accepted Submission(s): 34142

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

Sample Output

5 6 5 9

Hint

Huge input,the C function scanf() will work better than cin

Author

linle

Source

2007省赛集训队练习赛（6）_linle专场

Recommend

lcy | We have carefully selected several similar problems for you: 1698 1542 1394 2795 1540

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 200010;
 7 int n, m;
 8 struct segtree
 9 {
10     int l,r,v;
11 }T[N*4];
12 
13 void build(int l, int r, int k)
14 {
15     T[k].l = l, T[k].r = r;
16     if (l == r)
17     {
18         scanf("%d", &T[k].v);
19         return;
20     }
21     int mid = (l + r) / 2;
22     build(l, mid, k * 2);
23     build(mid + 1, r, k * 2 + 1);
24     T[k].v = max(T[k * 2].v, T[k * 2 + 1].v);
25 }
26 
27 int ans;
28 void query(int l, int r, int k)
29 {
30     if (l > T[k].r || r < T[k].l)
31     {
32         return;
33     }
34     if (l <= T[k].l && r >= T[k].r)
35     {
36         ans =max(ans,T[k].v);
37         return;
38     }
39     int mid = (T[k].l + T[k].r) / 2;
40     if (r < mid) query(l, r, 2 * k);
41     else if (l > mid) query(l, r, 2 * k + 1);
42     else
43     {
44         query(l, mid, k * 2);
45         query(mid + 1, r, k * 2 + 1);
46     }
47 }
48 
49 void Update(int c, int v, int k) 
50 {
51     if (T[k].l == T[k].r && T[k].l == c) 
52     {
53         T[k].v = v;
54         return;
55     }
56     int mid = (T[k].l + T[k].r) / 2;
57     if (c <= mid) Update(c, v, k * 2);
58     else Update(c, v, k * 2 + 1);
59     T[k].v = max(T[k * 2].v, T[k * 2 + 1].v);
60 }
61 int main()
62 {
63     while (~scanf("%d%d", &n, &m)) 
64     {
65         build(1, n, 1);
66         while (m--) 
67         {
68             char b[3];
69             int u, v;
70             scanf("%s", &b);
71             scanf("%d%d",&u, &v);
72             if (b[0] == 'U')
73                 Update(u, v, 1);
74             else if (b[0] == 'Q') 
75             {
76                 ans = 0;
77                 query(u, v, 1);
78                 printf("%d
", ans);
79             }
80         }
81     }
82     return 0;
83 }