问题 25316 --勤快的love 枫

25316: 勤快的love 枫

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 17
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][9000kb]

题目描述

小绝恋love 枫是一个出纳,经常需要做一些统计报表的工作。今天是绝恋love 枫的生日,小绝恋love 枫希望可以帮爸爸分担一些工作,作为他的生日礼物之一。经过仔细观察,小绝恋love 枫发现统计一张报表实际上是维护一个非负整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为N 的整数序列,并且有以下三种操作:INSERT i k 在原数列的第i 个元素后面添加一个新元素k;如果原数列的第i 个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子)

MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值

MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值)

例如一开始的序列为

5 3 1

执行操作INSERT 2 9 将得到:

5 3 9 1

此时MIN_GAP 2MIN_SORT_GAP 2

再执行操作INSERT 2 6 将得到:

5 3 9 6 1

注意这个时候原序列的第2 个元素后面已经添加了一个9,此时添加的6 应加在9 的后面。这个时候MIN_GAP 2MIN_SORT_GAP 1。于是小绝恋love 枫写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

输入

第一行包含两个整数N,M,分别表示原数列的长度以及操作的次数。

第二行为N 个整数,为初始序列。

接下来的M 行每行一个操作,即“INSERT i k”,“MIN_GAP”,“MIN_SORT_GAP”中的一种(无

多余空格或者空行)。

输出

对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。

样例输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

样例输出

2
2
1

提示


对于30% 的数据,N1000,M5000



对于100% 的数据,N,M50000



对于所有的数据,序列内的整数不超过5*108

来源

[提交][状态]