「KTSC 2022 R1」直方图 题解

问题分析

我们需要在直方图中选择不超过 $K$ 个不重叠的矩形，使得它们的面积之和最大。需要计算 $K=1,2,3$ 时的最大值。

关键难点：

• 矩形必须底边平行于地面，边长为整数
• 矩形之间不能重叠（除了顶点和边）
• 数据规模：$N \leq 5\times 10^5$

核心思路

算法框架

这是一个基于笛卡尔树分治和凸包合并的算法：

1. 笛卡尔树分解：将直方图转化为笛卡尔树，每个节点代表一个矩形区域
2. 分治求解：递归分解问题，合并子树信息
3. 凸包优化：维护面积关于矩形宽度的凸包，高效处理矩形组合
4. 李超树加速：使用李超线段树快速查询最优解

算法详解

笛卡尔树构建

for (int i = 1; i <= n; i++) {
    int lst = 0;
    t[i].h = H[i - 1];
    
    // 单调栈构建笛卡尔树
    while (tp && t[st[tp]].h > H[i - 1])
        lst = st[tp], tp--;
    
    if (lst) t[i].ls = lst;
    if (tp) t[st[tp]].rs = i;
    st[++tp] = i;
}

笛卡尔树性质：

• 每个节点对应一个以该节点高度为高的最大矩形
• 左子树对应当前矩形左侧区域
• 右子树对应当前矩形右侧区域

分治凸包合并

void cdx(int l, int r) {
    if (l == r) {
        // 构建当前区间的凸包
        chkconvex(vl[l]), chkconvex(vr[l]);
        return;
    }
    
    int mid = (l + r) >> 1;
    cdx(l, mid), cdx(mid + 1, r);
    
    // 合并左右子区间的凸包
    int i = 0, j = 0;
    while (i < x - 1 || j < y - 1) {
        // 双指针扫描凸包，找到最优组合
        chkmax(p[vr[mid][i].fi + vl[mid+1][j].fi], 
               vr[mid][i].se + vl[mid+1][j].se);
        // 根据斜率决定移动哪个指针
        (condition ? i : j)++;
    }
}

凸包维护原理：

• 每个点 $(w, area)$ 表示宽度为 $w$ 的矩形最大面积
• 维护上凸壳，保证斜率单调递减
• 合并时使用双指针找到最优组合

李超线段树优化

namespace lct {
    struct Node {
        Line l;  // 直线: y = kx + b
        int ls, rs;
    };
    
    void ins(int &x, int l, int r, Line a) {
        if (!x) x = newNode();
        int mid = (l + r) >> 1;
        
        // 在mid处比较，保留较优的直线
        if (getval(a, mid) > getval(t[x].l, mid))
            swap(a, t[x].l);
            
        // 递归插入到左右子树
        if (getval(a, l) > getval(t[x].l, l))
            ins(t[x].ls, l, mid, a);
        if (getval(a, r) > getval(t[x].l, r))
            ins(t[x].rs, mid + 1, r, a);
    }
    
    ll query(int x, int l, int r, int p) {
        if (!x) return 0;
        int mid = (l + r) >> 1;
        return max(getval(t[x].l, p), 
                   p <= mid ? query(t[x].ls, l, mid, p) 
                           : query(t[x].rs, mid + 1, r, p));
    }
}

李超树功能：

• 维护一组直线 $y = kx + b$
• 支持在 $x$ 处查询最大值
• 用于快速计算矩形组合的最优面积

子树信息合并

void dfs1(int u) {
    // 递归处理左右子树
    if (t[u].ls) dfs1(t[u].ls);
    if (t[u].rs) dfs1(t[u].rs);
    
    // 合并子树信息
    t[u].t1 = lct::merge(t[t[u].ls].t1, t[t[u].rs].t1, 1, m);
    t[u].t2 = lct::merge(t[t[u].ls].t2, t[t[u].rs].t2, 1, m);
    
    // 计算不同矩形数量的最优解
    ll tmp = (ll)t[u].h * t[u].l + lct::query(t[u].t1, 1, m, t[u].h);
    chkmax(f[u][2], tmp);
    chkmax(f[u][3], (ll)t[u].h * t[u].l + lct::query(t[u].t2, 1, m, t[u].h));
    
    // 更新李超树
    lct::ins(t[u].t1, 1, m, mkp((ll)t[u].h * t[u].l, -t[u].l));
    lct::ins(t[u].t2, 1, m, mkp(tmp, -t[u].l));
}

算法正确性

分治策略

算法采用经典的分治-合并框架：

$1.$ 分解：将直方图递归分解为更小的区间

$2.$ 解决：对每个区间计算凸包信息

$3.$ 合并：通过凸包合并得到更大区间的解

凸包性质

维护的凸包具有以下关键性质：

• 点 $(w, area)$ 表示选择宽度为 $w$ 的矩形能获得的最大面积
• 凸包上的点对应帕累托最优解
• 合并时只需考虑凸包上的点，大大减少计算量

复杂度分析

时间复杂度

• 笛卡尔树构建：$O(N)$
• 分治凸包合并：$O(N \log N)$
• 李超树操作：$O(\log M)$ 每次操作，$M$ 为高度范围
• 总复杂度：$O(N \log N \log M)$

空间复杂度

• 笛卡尔树：$O(N)$
• 凸包存储：$O(N \log N)$
• 李超树：$O(N \log M)$
• 总空间：$O(N \log N)$

算法优势

$1.$ 分治效率：$O(N \log N)$ 的分治框架处理大规模数据

$2.$ 凸包优化：利用凸包性质避免无效计算

$3.$ 李超树加速：快速查询和更新最优解

$4.$ 模块化设计：各组件职责清晰，易于理解和维护

总结

本题的解法展示了分治算法与计算几何技巧的完美结合：

$1.$ 笛卡尔树提供了问题的自然分解

$2.$ 凸包合并高效处理组合优化

$3.$ 李超树加速最优解查询

算法在 $O(N \log N \log M)$ 时间内解决了大规模直方图的最优矩形选择问题，体现了分治策略和几何优化在算法竞赛中的强大威力。