基于分块与链表数列操作及统计分析方法研究.pdfVIP

题目大意

•一个数列，支持以下操作

–一段数

–删除一段数

–统一修改一段数

–翻转一段数

–输出一段数的和

–求数列中和最大的一段非空子列并输出

数组/链表

•INSERT:O(N+tot)

•DELETE:O(N)

•MAKE-SAME:O(N+tot)

•REVERSE:O(N+tot)

•GET-SUM:O(N+tot)

•MAX-SUM:O(N)

•期望得分:50~70

分段

•数据结构

–使用单向链表将多个数组串联以信息

–每个数组中最多N个数

–相邻数组至少N个数

–最多需要O(N)个“块”（数组）

•细节：每一个“块”内记录

–输入数据

–“块”内总和/最大和

–从一端开始计算的最大部分和

–是否被翻转/统一修改的标志

分段(cont’d)

•:O(N+tot)•

•删除:O(N);–在、删除、修改、

•修改:O(N);翻转操作

•翻转:O(N);–段内的附加值如总

•求和:O(N);和/最大和等等

•最大和:O(N)。–合并可能出现的“碎片”

以保证段的个数不会太

多

•期望得分：100–时间复杂度O(N)

平衡二叉树

•为数列建立一棵平衡二叉树

–:O(logN+tot)

2

–其他操作时间复杂度均为O(logN)

2

•细节

–!@#$!@#$

•期望得分：？？