Description
很多學校流行一種比較的習慣。老師們很喜歡詢問，從某某到某某當中，分數最高的是多少。Input
本題目包含多組測試，請處理到文件結束。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
題目大意：中文題目，不解釋。
解題思路：用線段樹儲存學生成績。注意，建樹過程中，父節點值為子節點中的最大值；修改過程中，要更新整棵線段樹；查找過程要注意邊界。
#include#include #include #include using namespace std; #define NUM 200000 int N, M; int S[4 * NUM], V[4 * NUM], R[4 * NUM], L[4* NUM]; void build(int n, int l, int r) { //建線段樹 if (l == r) { R[n] = l; L[n] = l; S[n] = V[l - 1]; return ; } else { int temp = (l + r) / 2; R[2 * n + 1] = temp; R[2 * n + 2] = r; L[2 * n + 1] = l; L[2 * n + 2] = temp + 1; build(2 * n + 1, L[2 * n + 1] , R[2 * n + 1]); build(2 * n + 2, L[2 * n + 2], R[2 * n + 2]); S[n] = max(S[2 * n + 1], S[2 * n + 2]); } return ; } void modify(int n, int x, int v) { //將X改為V if (L[n] == x && R[n] == x) { S[n] = v; return; } int mid = (L[n] + R[n]) / 2; if (x <= mid) { modify(n * 2 + 1, x, v); } else { modify(n * 2 + 2, x, v); } S[n] = max(S[n * 2 + 1], S[n * 2 + 2]); } int cnt; int find(int n, int l, int r) { //查找區間l到r的最大值 if (l <= L[n] && r >= R[n]) { return S[n]; } int mid = (L[n] + R[n]) / 2; int min = -1; if (l <= mid) { min = max(min, find(n * 2 + 1, l, r)); } if (r > mid) { min = max(min, find(n * 2 + 2, l, r)); } return min; } int main() { while (scanf("%d %d\n", &N, & M) != EOF) { memset(S, 0, sizeof(S)); memset(V, 0, sizeof(V)); memset(R, 0, sizeof(R)); memset(L, 0, sizeof(L)); int cnt = 0; for (int i = 0; i < N; i++) { scanf("%d ", &V[cnt++]); } L[0] = 1; R[0] = cnt; build(0, L[0], R[0]); char ch; for (int i = 0; i < M; i++) { scanf("%c ", &ch); if (ch == 'Q') { int a, b; scanf("%d %d\n", &a, &b); printf("%d\n", find(0, a, b)); } else if (ch == 'U') { int a, b; scanf("%d %d\n", &a, &b); modify(0, a, b); } } } return 0; }
