天网

Grade 100 Open Time Thursday, 18 June 2020, 5:25 PM
Discount 0.8 Time Discount Thursday, 18 June 2020, 5:25 PM
Allow late Yes Close Time Thursday, 18 June 2020, 5:25 PM
Input file SkyNet.in Output file SkyNet.out

【题目描述】天网(SkyNet)HDU 1754

除了了解小光舰队的某一段连续的堡垒一共有多少飞船以外,琪儿还会询问从某某堡垒到某某堡垒当中,飞船数最多的是多少。

现在请你写一个程序,模拟回答琪儿的询问。当然,小光有时候会改变某个堡垒中的飞船数。

【输入格式】

本题目包含多组测试,请处理到文件结束。

在每个测试的第一行,有两个正整数 N 和 M ( 0<N≤200 000,0<M<5 000 ),分别代表堡垒的数目和操作的数目。

堡垒编号分别从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。

【输出格式】

对于每一次询问操作,在一行里面输出最多飞船数。

【输入样例】

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

【输出样例】

5

6

5

9