题解归档 - cf2234F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2234F
• 本地来源：problems/cf2234F/idea.md
• 题目链接：https://codeforces.com/contest/2234/problem/F
• 原始标题：cf2234F 思路总结

思路

cf2234F 思路总结

Vessels, Heights and Two Versions (Hard) — 题意与 C 完全相同，仅数据更大。
C 思路见 problems/cf2234C/idea.md（已 AC）。

1. 题意（一句话）

(n) 个容器围成环，隔板 (h_i) 在容器 (i) 与 (i+1) 之间。数组 (w) 合法 ⟺ 若相邻 (\max(w_i,w_{i+1})>h_i) 则必须 (w_i=w_{i+1})。

对每个空点 (l)（(w_l=0)），求 (\sum w_i) 的最大值。

官方样例（与 C 相同）：(n=4,h=[1,2,3,4]) → ans = [6,6,7,9]。

2.5 破局：在全局 max 隔板处切环（已验证）

设 (M=\max h)，取任一满足 (h_m=M) 的隔板 (m)（若多个取其一即可）。

对任意空点 (l)、容器 (i)（(l\ne i)），环上两条简单路径：

• 过 (m) 的那条：路径 max (=M)（必含全局最大隔板）
• 不过 (m) 的那条：路径 max (=X\le M)

故

[
w_i=\min(X,M)=X=\text{（不过 }m\text{ 那条路径上的 }\max h\text{）}
]

推论：不再需要 (\min) 双路、不需要 crossover；环拆成 删掉边 (m) 后的 一条链，(w_i) = 链上 (l\to i) 唯一路径的 max。

链上形式

顶点顺序（0-index）：((m+1),(m+2),\ldots,(m-1))，共 (n) 个点。
边为 (h[m+1],h[m+2],\ldots,h[m-1])（不含 (h[m])），长度 (n-1)，且 每条边高度 (<M)（若 (M) 唯一）。

空点在链上位置 (p)，容器在 (q)：

[
w=\max\bigl(\text{边 }e[\min(p,q)\,..\, \max(p,q)-1]\bigr)
]

[
\text{ans}[p]=\sum_{q\ne p} w(p,q)
]

验证：explore_cut.py，500 组随机与 ref 一致。

单调栈：要算什么

链上只有 (n-1) 条边 (e[0..n-2])。对每个空点位置 (p)：

[
\text{ans}[p]=\underbrace{\sum_{q<p}\max(e[q..p-1])}_{\text{向左 L}(p)}+
\underbrace{\sum_{q>p}\max(e[p..q-1])}_{\text{向右 R}(p)}
]

• 向右 (R(p))：固定起点 (p)，终点 (q) 右移，前缀 max 只增 → 经典「向右扩展」
• 向左 (L(p))：对称，等价于把数组反转再算一遍 (R)

目标：所有 (p) 的 (L(p)+R(p)) 在 (O(n)) 求出。

单调栈细节（向右 (R(p))）

对 固定 (p)，设 (g_k=\max(e[p..k]))（(k\ge p)），则 (R(p)=\sum_{k=p}^{n-2} g_k)（对应顶点 (k+1)）。

当 (p) 从 (n-1) 减到 (0) 时，在 (e[p-1]) 前插入新边；栈维护 递减 的 ((\text{值},\text{该值作为 max 能覆盖的右端点数}))：

1. 新边 (e[p]) 入栈前，弹出所有栈顶 值 (\le e[p])（它们不可能再成为更大区间的 max）
2. 弹出时把「被 (e[p]) 盖掉」的右端贡献累加
3. 栈中每个值 (v) 表示：存在一段右端区间，以 (v) 为路径 max 的和对 当前及更左的 (p) 有贡献

对称地 从右往左扫 一遍得所有 (L(p))。两遍栈 (O(n))。

（实现时可参考：子数组最大值之和 / 每个元素作为区间 max 的 PGE-NGE 贡献；此处是「固定起点」版本，但栈结构同类。）

与旧思路的关系

solution.cpp 已按这个形式实现：选一个全局最大隔板 m，删掉它把环变成链；两次 scan 分别计算每个空点向右、向左的区间最大值总和。注意 h_m=M 可以不唯一，任选一个最大下标即可，因为不过该边的那条路径最大值不超过 M。

2. 已证核心公式（C / 对拍基准）

固定空容器 (l)，对每个 (i\ne l)：

• (R_i)：从 (l) 顺时针走到 (i) 路径上 (\max h)
• (L_i)：从 (l) 逆时针走到 (i) 路径上 (\max h)
• 最优水位：(w_i = \min(L_i, R_i))

ans[l] = sum_{i != l} min(L_i, R_i)

• 每个 (l) 两次扫描：(O(n))
• 所有 (l)：(O(n^2)) — F 必 TLE（当前 solution.cpp / brute.cpp 均为此实现）

3. 图论 / 三点 gadget 建模（已验证）

每容器拆 3 点：L_i — C_i — R_i，隔板 (h_i) 连 R_i 与 L_{i+1}。

并查集 / 阈值合并：对固定空点 (l) 可理解为「按 (h) 合并必须同高的块 + 双路瓶颈」，与上式等价；Hard 难点是对所有 (l) 同时聚合。

验证：explore.py（n=4,h=[1,2,3,4] + 随机小数据 vs dfs 暴力）。

4. 固定容器 (i) 的贡献分解（选定方向）

[
\text{ans}[l] = \sum_{i=1}^{n} c_i[l], \quad c_i[l] = \begin{cases} 0 & l=i \ \min(F_i(l), G_i(l)) & l\ne i \end{cases}
]

• (F_i(l))：空点 (l)、容器 (i) 的顺弧 (\max h)
• (G_i(l))：同一 ((l,i)) 的逆弧 (\max h)

固定 (i)，空点 (l) 按 (i+1,i+2,\ldots,i-1) 绕圈：

• (F_i(l)) 不增（顺弧变短）
• (G_i(l)) 不减（逆弧变长）
• (\min(F,G)) 先跟 (G) 后跟 (F)，至多一个 crossover

单点 (i) 可 (O(n)) 扫；(n) 个 (i) 合计仍 (O(n^2))。

验证：explore_contrib.py（分解与 ref 一致；contrib_i_fast 增量扫 (l)）。

固定 (i) 贡献行示例（(h=[1,2,3,4])）：

5. 固定空点 (l)：前缀 / 后缀视角

在 (l) 处断开环，顺时针编号 (k=1..n-1)，容器 (v=(l+k)\bmod n)：

(l=1, h=[1,2,3,4])：

和 = 6 = ans[1]。

注意：(G) 在最后一个容器（(l) 的逆时针邻）可能 断崖（例：(l=2) 时 (G=[4,4,1])）。

单点 (l) 求 (\sum\min)：找 crossover（(F) 从 ≤ 变 ≥ (G)），前缀用 (G)、后缀用 (F) — (O(n))。

Hard 不能只维护一套全局前缀后缀：断点 (l) 一变，两弧 max 全变。

6. 阈值 (H) 与存活区间 ([s,t])（已验证）

恒等式（整数水位）：

[
\text{ans}[l] = \sum_{H=1}^{H_{\max}} \text{cnt}l
]

(\text{cnt}l) = 满足 (F_i(l)\ge H) 且 (G_i(l)\ge H) 的容器 (i) 个数（等价于 (\min(F,G)\ge H)）。

重要：必须对 每个整数 (H) 累加，不能只取 distinct(h)。
反例：(h=[5,1,3,1])，缺 (H=2) 会把 7 算成 5。

对固定 ((l,H))，令 (k) 为顺时针距离（(k=1..n-1)）：

• (F(k)) 随 (k) 不降 → (F\ge H) ⟺ (k\ge s)（后缀）
• (G(k)) 随 (k) 不升 → (G\ge H) ⟺ (k\le t)（前缀）
• 存活 (k \in [s,t])，(\text{cnt}l = \max(0,\, t-s+1))

(n=4, h=[1,2,3,4], H=2)：

全局：(N(1)=12,\ N(2)=10,\ N(3)=6,\ N(4)=0)；(\sum_H N(H)=28=\sum_l \text{ans}[l])。

验证：explore_threshold.py（[s,t] 公式 + 完整 (H) 循环 vs ref，300 组随机）。

7. 手算全表（(n=4, h=[1,2,3,4])）

7.1 ((l,i)) → (F, G, \min)

（表中数字为 (w_i=\min(F,G))）

7.2 规律摘要

1. 瓶颈 = 两弧 max 的较小者，非独立分配水量
2. 固定 (l)：(F) 升、(G) 在绕回邻点处可能跳水
3. 阈值淘汰：(H) 升高时，先淘汰「短弧 max 不足」的 ((l,i))（如 (H=2) 淘汰 (1,2),(2,1)）
4. 全局 max：(h_{\max}=4) 但 (N(4)=0)，单容器水位到不了 4
5. 存活结构：对每个 ((l,H))，存活 (i) 在顺时针序下是 连续区间 ([s,t])

8. 复杂度与卡点

9. 本地文件与验证

problems/cf2234F/
├── solution.cpp      # 当前 = C 的 O(n²) 占位
├── brute.cpp         # O(n²) 对拍基准
├── dfs.cpp           # n≤8 指数暴力
├── gen.cpp           # n∈[3,100]
├── sample.in/out
├── explore.py        # 三点 gadget + ref vs dfs
├── explore_contrib.py # 固定 i 贡献分解
├── explore_cut.py      # 切环公式 vs ref
└── idea.md           # 本文

对拍：python tools/stress.py cf2234F -n 500

10. 下一步

• [x] 实现 §2.5：找 (m=\arg\max h)，建链，两遍单调栈求 (L(p)+R(p))
• [x] solution vs brute 对拍 500 组
• [ ] 提交 F

实现要点：正向 scan 得 (R(p)=\texttt{ss}[p])；边数组反转后再 scan 得 (\texttt{Fr})，则 (L(p)=\texttt{Fr}[n-1-p])（不是 (\texttt{Fr}[p])）。栈弹出条件为严格 <。

最后更新：2026-06-08 — O(n) 切环+单调栈 AC 本地对拍。

代码

来源：problems/cf2234F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 01:00:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll h[maxn+5],e[maxn+5],ss[maxn+5],ans[maxn+5],pos[maxn+5];
struct nd{
    ll v,c;
};
nd st[maxn+5];
void scan(ll n,ll*out){
    ll i,top=0,cur=0,cnt;
    if(n<=1){
        for(i=0;i<n;i++) out[i]=0;
        return;
    }
    out[n-1]=0;
    for(i=n-2;i>=0;i--){
        cnt=1;
        while(top>0 and st[top].v<e[i]){
            cur-=st[top].v*st[top].c;
            cnt+=st[top].c;
            top--;
        }
        cur+=e[i]*cnt;
        top++;
        st[top].v=e[i];
        st[top].c=cnt;
        out[i]=cur;
    }
}
int main(){
    ll t,n,i,m0,p,v;
    cin>>t;
    while(t--){
        cin>>n;
        m0=1;
        for(i=1;i<=n;i++){
            cin>>h[i];
            if(h[i]>=h[m0]) m0=i;
        }
        for(p=0;p<n;p++){
            v=(m0%n+p)%n+1;
            pos[v]=p;
        }
        for(p=0;p<n-1;p++){
            v=(m0%n+p)%n+1;
            e[p]=h[v];
        }
        scan(n,ss);
        for(i=1;i<=n;i++) ans[i]=ss[pos[i]];
        for(p=0;p<n-1;p++) e[p]=h[(m0%n+n-2-p)%n+1];
        scan(n,ss);
        for(i=1;i<=n;i++) ans[i]+=ss[n-1-pos[i]];
        for(i=1;i<=n;i++){
            cout<<ans[i];
            if(i==n) cout<<"\n";
            else cout<<" ";
        }
    }
    return 0;
}