UOI 2023 Stage 4 Day1 - 数组与部分和 题解

题目概述

给定一个长度为 $n$ 的整数数组 $a$，其中每个元素的值在 $-1$ 到 $1$ 之间。我们可以执行三种操作：

1. 取反操作：将数组中所有元素变为相反数
2. 前缀和操作：选择任意子区间，将其替换为该子区间的前缀和数组，然后进行归一化（将元素限制在 $[-10^{18}, 10^{18}]$ 范围内）
3. 后缀和操作：选择任意子区间，将其替换为该子区间的后缀和数组，然后进行归一化

目标是通过最少的操作序列，使得数组中的所有元素都变为非负数。

解题思路

关键观察

1. 操作的本质：前缀和和后缀和操作实际上是在对数组进行线性变换，这些变换会改变数组中元素的分布
2. 归一化的作用：防止数值溢出，但由于输入范围很小（-1到1），在实际操作中很少会触发
3. 对称性：取反操作可以改变整个数组的符号，这为解决某些情况提供了便利

解决方案

题目采用分层解决的策略，从简单情况到复杂情况逐步处理：

情况1：0次操作

直接检查原数组是否已经满足所有元素非负。

情况2：1次操作

检查三种可能的单步操作是否能解决问题：

• 取反操作
• 对整个数组执行前缀和操作
• 对整个数组执行后缀和操作

情况3：2次操作

这是最复杂的情况，需要深入分析：

1. 先取反再执行前缀和/后缀和操作
2. 分析前缀和数组的性质，寻找合适的操作区间
3. 使用凸包优化来高效计算可能的解

算法核心

代码中的核心部分使用凸包优化来寻找满足条件的操作区间：

1. 前缀和计算：计算数组的前缀和 pre[i] 和前缀和的前缀和 ppre[i]
2. 凸包构建：将问题转化为在二维平面上寻找满足条件的线段
3. 二分查找：在凸包上快速找到最优解

特殊情况处理

当上述方法都无法在2步内解决问题时，代码采用一个通用的3步解决方案：

1. 如果需要，先执行取反操作
2. 对数组后半部分执行前缀和操作
3. 对数组前半部分执行后缀和操作

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自凸包构建和二分查找
• 空间复杂度：$O(n)$，用于存储各种前缀和数组和凸包

代码实现要点

1. 操作模拟：实现了三种操作的具体逻辑
2. 快速检查：分层检查0、1、2步解决方案
3. 凸包优化：使用栈维护凸包，通过二分查找快速确定最优解
4. 边界处理：仔细处理各种边界情况，确保算法正确性

总结

这道题的关键在于理解前缀和和后缀和操作对数组的变换效果，并通过分层处理和凸包优化来寻找最优解。算法设计巧妙，既考虑了简单情况的快速解决，又为复杂情况提供了高效的解决方案。

对于竞赛选手来说，这道题考察了以下几个重要能力：

• 对线性变换的理解
• 凸包优化的应用
• 问题分解和分层解决策略
• 边界情况的处理能力