HBC20600[ZJOI2007]报表统计题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

小Q的妈妈是一个出纳，经常需要做一些统计报表的工作， 今天是妈妈的生日，小Q希望可以帮妈妈分担一些工 作，作为她的生日礼物之一， 经过仔细观察，小Q发现统计一张报表实际上是维护一个可能为负数的整数数列，并且进行一些查询操作， 在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作： INSERT i k 在原数 列的第i个元素后面添加一

小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。 今天是妈妈的生日，小Q希望可以帮妈妈分担一些工 作，作为她的生日礼物之一。 经过仔细观察，小Q发现统计一张报表实际上是维护一个可能为负数的整数数列，并且进行一些查询操作。 在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作：  INSERT i k 在原数 列的第i个元素后面添加一个新元素k； 如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（ 见下面的例子）  MIN_GAP 查询相邻两个元素的之间差值（绝对值）的最小值  MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值（绝对值）  例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到： 5 3 9 1 此时MIN_GAP 为2，MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到： 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经 添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为1。 于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？

标签： HBC20600[ZJOI2007]报表统计题解