N哒--询问、更新--数据

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

这是个什么问题呢?DP,贪心,数据结构,图论,数论还是计算几何?管他呢,反正胖巨巨都会,虽然胖巨巨走得早。
 
给出n个数,编号从1到n。接下来m次操作,每次操作为下述两种形式的一种:
(1)询问,给出编号L,R(1 <= L <= R <= n),询问[L,R]中最大值与最小值之差。
(2)更新,给出编号d(1 <= d <= n),及值x(1 <= x <= 10000),将编号为d的值更新为x。
温馨提示:记得用%s输入。

Input

多组输入。对于每组输入:
第一行输入n,m(1 <= n <= 100000,1 <= m <= 10000)。
接下来一行包含n个数。
接下来m行描述m次操作,格式为char intx inty,若char为 'Q',则表示此次操作为询问[intx,inty]的最值之差,若char为'U',则此次操作是将编号为intx的数更新为inty。

Output

对于每次询问输出一个整数代表[L,R]总最大值与最小值之差。
具体格式见样例。

Sample Input

3 3
1 2 3
Q 1 3
U 2 100
Q 2 3

Sample Output

2
97

Hint

 

Source

zmx