1220. intelligence

单点时限: 3.0 sec

内存限制: 256 MB

One day , sunny’s classmates ask him for help,because they meet a very difficult problem .They want to calculate the highest number in a given interval ,and it may change some number.how do you solve it.

输入格式

First input two numbers n (n<=200000)and m(m<=5000),n stand for the interval’s range from 1 to n,m stand for the time of operation.

The second line input n numbers stand for the initialization number in n place

Then following m line ,if the first is a letter Q ,stand for asking, then follow two numbers A,B ,mean ask the highest number in the interval from A to B.Out put the number in a line.

if it is a letter U , and follow two numbers A B(A<=B),mean you must change the position A’s number to B.Output nothing.

输出格式

For each Q ,output the highestnumber in the given interval [A,B].

样例

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
Output
5
6
5
9

12 人解决,32 人已尝试。

21 份提交通过,共有 161 份提交。

7.2 EMB 奖励。

创建: 13 年前.

修改: 2 年,9 月前.

最后提交: 4 年,5 月前.

来源: LSP

题目标签