I Hate It
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
HintHuge input,the C function scanf() will work better than cin
Author
linle
题目类型：线段树
算法分析：线段树的单点更新和区间查询，直接建立线段树求解即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 10000007; const int maxn = 200000; int maxval[maxn<<2]; void PushUp (int rt) { maxval[rt] = max (maxval[rt<<1], maxval[rt<<1|1]); } void Build (int rt, int l, int r) { if (l == r) { scanf("%d", &maxval[rt]); return ; } int m = (l + r) >> 1; Build (lson); Build (rson); PushUp (rt); } void UpDate (int rt, int l, int r, int p, int add) { if (l == r) { maxval[rt] = add; return ; } int m = (l + r) >> 1; if (p <= m) UpDate (lson, p, add); else UpDate (rson, p, add); PushUp (rt); } int Query (int rt, int l, int r, int L, int R) { if (L <= l && r <= R) { return maxval[rt]; } int m = (l + r) >> 1; int ans = -INF; if (L <= m) ans = max (ans, Query (lson, L, R)); if (R > m) ans = max (ans, Query (rson, L, R)); return ans; } int main() { // freopen ("aaa.txt", "r", stdin); int n, m; while (scanf ("%d%d", &n, &m) != EOF) { Build (1, 1, n); char cmd[6]; int val_a, val_b; int i; for (i = 0; i < m; i++) { scanf ("%s%d%d", cmd, &val_a, &val_b); if (cmd[0] == 'Q') printf ("%d\n", Query (1, 1, n, val_a, val_b)); else UpDate (1, 1, n, val_a, val_b); } } return 0; } |
- « 上一篇：hdu1712
- hdu1788：下一篇 »