BZOJ 4864: [BeiJing 2017 Wc]神秘物质(splay)

Description

21ZZ 年,冬。
小诚退休以后, 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器,整天研究各种微观粒子。这
一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始观测。 在精密仪器的视野下,构成陨石
的每个原子都无比清晰。 小诚发现, 这些原子排成若干列, 每一列的结构具有高度相似性。于是,他决定对单
独一列原子进行测量和测试。被选中的这列共有 N 个顺序排列的原子。 最初, 第 i 个原子具有能量 Ei。 随着
时间推移和人为测试, 这列原子在观测上会产生两种变化:
merge x e 当前第 x 个原子和第 x+1 个原子合并,得到能量为 e 的新原子;
insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子。
对于一列原子,小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值,
称为区间极差。 因此, 除了观测变化外,小诚还要经常统计这列原子的两类数据:
max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值;
min x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。
其中, 子区间指的是长度至少是 2 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿,你能否帮助他实现上述的观测和测量呢?
Input

第一行, 两个整数 N, M, 分别表示最初的原子数目和事件总数。
第二行, N 个整数 E1, E2, …, EN, 由空格隔开。依次表示每个原子的能量。
接下来 M 行, 每行为一个字符串和两个整数, 描述一次事件,格式见题目描述。
N<=100,000,M<=100,000 1 ≤ e, Ei ≤ 109。 设 N’ 为当前时刻原子数目。 对于 merge 类事件, 1 ≤ x ≤ N’-1; 对于 insert 类事件, 1 ≤ x ≤ N’; 对于 max 和 min 类事件, 1 ≤ x < y ≤ N’。 任何时刻,保证 N’ ≥ 2。 Output 输出若干行, 按顺序依次表示每次 max 和 min 类事件的测量结果。 Sample Input 4 3 5 8 10 2 max 1 3 min 1 3 max 2 4 Sample Output 5 2 8 一个细节很多的题目。。。调了半天。。 因为随着一个区间的长度增大,其最大值减最小值的差值也会越来越大。所以对于一个区间来说,其极差最大的子区间就是整个区间,其极差最小的区间必然是相邻的两个数。 splay维护区间最大值和最小值,以及相邻两个数的差值即可。在插入和删除的时候修改相邻的两个数的差值(注意这里一定要把两个数都旋转到当前节点的左右两侧)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注