天网
成绩 | 100 | 开启时间 | 2020年06月18日 星期四 17:25 |
折扣 | 0.8 | 折扣时间 | 2020年06月18日 星期四 17:25 |
允许迟交 | 是 | 关闭时间 | 2020年06月18日 星期四 17:25 |
输入文件 | SkyNet.in | 输出文件 | 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