OI题库

问题描述

某国地形狭长，中部有一列山脉，由于多发地震，山脉在不断变化中。地震发生时，山脉有可能发生如下变化：局部海拔升高或降低，板块运动产生地裂而出现一段新的山脉，或板块挤压迫使一段山脉消失。

该国的科学考察队已经预测出了近期内将要发生的一次地震的全过程，他们得到的山脉变化的信息数据格式如下。

R a b c

a,b,c为三个整数，表示[a,b]这段山脉的海拔升高了c（或降低了-c）。

I a k t1 t2 ... tk

a,k,t1,t2,...,tk为整数，在第a个位置之后出现了一段新的山脉，长度为k，各处海拔依次为t1,t2,...,tk。

M a b

a,b为两个整数，表示[a,b]这段山脉消失，后面的山脉会移动过来。

查询请求格式为

Q a b

a,b为两个整数，查询[a,b]这段山脉的最高峰的海拔。

现在他们想知道这次地震中任意时刻任意一段山脉的最高峰的海拔，请你设计程序帮助他们。

输入格式

第一行，两个整数N,Q，表示地震前山脉的长度为N，地震中有Q个事件。 第二行，N个整数，表示初始时山脉各处的海拔。 接下来Q行，每行为一个山脉变化信息或查询请求，格式如上。

输出格式

对于每一个查询请求，输出一行，为该查询请求的结果。

样例输入

10 7
1 3 4 6 3 5 9 1 4 5
R 1 4 2
Q 3 7
I 1 2 2 3
M 6 9
Q 2 5
R 1 6 -4
Q 1 3

样例输出

9
6
-1

样例说明

初始时刻，山脉各处海拔为

1 3 4 6 3 5 9 1 4 5

经过 R 1 4 2，山脉各处海拔为

3 5 6 8 3 5 9 1 4 5

查询Q 3 7，结果为9

I 1 2 2 3，在1第个位置后插入了长度为2的山脉2 3，之后山脉各处海拔为

3 2 3 5 6 8 3 5 9 1 4 5

M 6 9后，山脉各处海拔为

3 2 3 5 6 1 4 5

查询Q 2 5，结果为6

经过 R 1 6 -4，山脉各处海拔为

-1 -2 -1 1 2 -3 4 5

查询Q 1 3，结果为-1

数据规模

• 对于40%的数据，Q<=10000。
• 对于70%的数据，1<=Q<=100000。
• 对于100%的数据，1<=Q<=300000。

在任何时刻，山脉的长度在[1,100000]之内，山脉各处海拔在[-2^31,2^31]之内。初始山脉长度连同插入的山脉的总长度不超过1000000。在所有请求中，插入山脉(I)、压入地下(M)、查询(Q)、升降(R)、的比例约为2:3:3:4。