基本信息项目内容题目编号、来源P11963/luogu训练层级B 变式题知识版块数据结构 / 单调队列 / 前缀和 / 环形数组处理解题前 · 关键信号识别维度分析目标、约束、底层结构目标求首尾相连的环形数组中长度不超过n的连续子数组的最大和约束数组环形首尾相接、子段长度不能超过n底层结构环形区间最值转化为线性滑动窗口最值问题。数据规模n≤2×10^5破环成链需要开2倍数组总长度4e5足够数值累加范围大必须使用long long防止溢出。候选算法和依据破环成链 前缀和 单调队列依据区间和可通过前缀和转化为sum[i]-sum[L]的差固定窗口长度n求最小值用单调递增队列环形问题通过复制数组转化为线性问题暴力O(n²)会超时。复杂度预判O(n)仅一次遍历2n长度数组每个元素仅入队、出队各一次无嵌套循环可通过2e5大数据。解题后 · 外化复盘从会一次到稳定会维度内容实现结构 / 核心思路第一步破环成链把原数组复制一遍接在尾部将环形区间转化为2n长度线性数组中长度≤n的连续区间第二步前缀和将区间求和转化为两个前缀和的差值第三步单调队列用单调递增队列维护窗口内最小的前缀和下标,如果head与tail相差大于n则必须head然后取ans和sum[i]与sum[q[head]]的差值然后sum[q[tail]]sum[i]则tail–使队列单调递增错因回溯逻辑BUG / 代码实现BUG数组开int类型导致累加溢出忘记初始化ans为极小值全负数数组答案错误入队顺序写在更新答案前导致L和i重合。边界和易错点1. 数组必须开2倍以上长度破环成链避免下标越界2. 窗口长度判断条件是i-q[head]n注意等号边界3. 求最小前缀和必须用单调递增队列判断符号不能写反4. 全部数值用long long防止多轮累加爆int5. ans初始化为极小值如-1e10适配全负数数组6. 必须先更新答案再将i入队保证子段左端点严格小于右端点。下次看到什么信号我应该想到这个方法看到「环形数组 连续子段最大/最小和 限制子段长度 数据规模1e5以上暴力超时」优先想到破环成链前缀和单调队列滑动窗口。AC 完整代码#includeiostream#includequeueusingnamespacestd;usinglllonglong;constll N4e510;ll n,a[N],sum[N],q[N],head1,tail,ans-1e10;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){cina[i];a[in]a[i];}for(ll i1;in*2;i){sum[i]sum[i-1]a[i];}for(ll i1;in*2;i){while(headtaili-q[head]n)head;ansmax(ans,sum[i]-sum[q[head]]);while(headtailsum[q[tail]]sum[i])tail--;q[tail]i;}coutans;return0;}