输入描述:
|
1
2
3
4
5
6
|
输入包括多组测试数据。
每组输入第一行是两个正整数N和M（0 < N <= 30000,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。
|
输出描述:
|
1
|
对于每一次询问操作，在一行里面输出最高成绩.
|
输入例子:
|
1
2
3
4
5
6
7
8
9
|
5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5
|
输出例子:
|
1
2
3
4
|
5
6
5
9
|
#define CHECK_N(x) (x>0 && x<=30000) #define CHECK_M(x) (x>0 && x<=5000) //在制定范围找出最大值 int Query_Max(int *a, int n, int top, int bottom) { int max; if (top >= 0 && bottom >= top && bottom <= n) { max = a[top]; for (int i = top; i < bottom; i++) { if (max <= a[i]) { max = a[i]; } } } return max; } int main(int argc,char** argv) { //int a[] = { 4, 2, 8, 11, 3, 55, 7, 9, 10 }; //QuickSort(a, 0, sizeof(a) / sizeof(a[0])-1); int N, M; scanf("%d %d", &N, &M); int *grade = new int[N]; int *result = new int[M]; int Q_time = 0; if (!CHECK_M(M) || !CHECK_N(N)) return -1; for (int i = 0; i < N; i++) { cin >> grade[i]; } for (int i = 0; i < M; i++) { char c; int line[2] = { 0, 0 }; cin >> c >> line[0] >> line[1]; if (c == 'U') { grade[line[0] - 1] = line[1]; } if (c == 'Q') { result[Q_time++] = Query_Max(grade, N, line[0]-1, line[1]); } } for (int i = 0; i < Q_time; i++) { cout << result[i] << endl; } return 0; }