算法思路

核心思想

使用**线段树套ODT（珂朵莉树）**的组合数据结构，高效处理区间染色和最小值更新操作。

数据结构设计

1. 外层线段树（按行维护）

• 维护信息：
  • mn：区间内行的最小美观度
  • sm：区间内行的最小列号（用于计算美观度）
  • cnt：具有最小美观度的行数
  • sum：区间权值和
  • ad1：全区间加的懒标记
  • ad2：最小值区间加的懒标记

2. 内层ODT（按列维护）

• 每个列维护一个珂朵莉树，存储该列的连续染色段
• 快速处理区间染色操作（黑白染色）

关键操作实现

染色操作（操作1、2）

void upd(int l, int r, bool t) {
    // 使用ODT进行区间染色
    // 更新线段树中的美观度信息
}

• 时间复杂度：均摊 $O(\log n)$

最小值更新（操作3）

void upd2(int p, int l, int r, int gl, int gr, int k, int mn, ll v) {
    // 找到区间内美观度最小的行
    // 对这些行进行权值更新
}

• 时间复杂度：$O(\log n)$

查询操作（操作4）

ll qry2(int p, int l, int r, int gl, int gr) {
    // 查询区间权值和
}

• 时间复杂度：$O(\log n)$

算法优势

1. 高效处理区间染色：ODT适合大量区间赋值操作
2. 快速最小值查询：线段树维护区间最小值信息
3. 双重懒标记：分别处理全区间加和最小值区间加
4. 颜色段均摊：ODT保证操作次数的均摊复杂度

复杂度分析

• 预处理：$O(n \log n)$
• 每次操作：$O(\log^2 n)$（最坏情况）
• 总复杂度：$O(m \log^2 n)$

适用场景

• 大规模区间染色操作
• 需要动态维护区间极值
• 操作类型多样的复杂场景

该算法通过组合数据结构的巧妙设计，在保证效率的同时解决了复杂的操作需求。