题解：ROI 2024 Day1「拉马赞与卷心菜」

问题分析

题目要求统计所有满足条件的水平线段 $(x_1, x_2, y)$，其中：

• 线段上所有点 $(x, y)$（$x_1 \leq x \leq x_2$）都属于种植区
• 线段左右相邻点 $(x_1-1, y)$ 和 $(x_2+1, y)$ 都不属于种植区

我们需要统计：

1. 所有不同的 $(x_1, x_2)$ 对
2. 每个 $(x_1, x_2)$ 对出现的行数 $cnt$
3. 每个 $(x_1, x_2)$ 对连续出现的最大行数 $k$

算法思路

核心观察

水平线段 $(x_1, x_2, y)$ 满足条件当且仅当：

• 在 $y$ 行上，区间 $[x_1, x_2]$ 完全被覆盖（种植卷心菜）
• 在 $y$ 行上，点 $x_1-1$ 和 $x_2+1$ 未被覆盖

扫描线算法

使用垂直扫描线从左到右扫描 $x$ 坐标，同时维护当前 $y$ 轴上的覆盖情况。

数据结构设计

• 离散化：将 $y$ 坐标离散化，建立线段树
• 线段树：维护每个 $y$ 区间上的覆盖次数和连续段信息

线段树维护的信息

对于每个节点维护：

• mncnt：最小覆盖次数
• appcnt：达到最小覆盖次数的区间总长度
• mnl, mxl：最小/最大 $x$ 值（用于标识连续段）
• lft, rgt：左右连续段长度
• seg：中间最大连续段长度
• totl：节点对应区间总长度

关键操作

1. 更新操作：处理矩形的加入和删除

   • 加入矩形：对应 $y$ 区间覆盖次数+1，记录当前 $x$ 坐标
   • 删除矩形：对应 $y$ 区间覆盖次数-1

2. 查询操作：在扫描线移动时，查询当前所有覆盖次数为0的连续段

   • 这些连续段对应有效的水平线段
   • 记录 $(x_1, x_2)$ 对的出现情况和连续性

代码实现详解

数据结构初始化

void build(int k, int l, int r, int *x) {
    // 初始化线段树节点
    mncnt[k] = appcnt[k] = mnl[k] = mxl[k] = lft[k] = rgt[k] = seg[k] = 0;
    totl[k] = ad[k] = 0;
    laz[k] = -1;
    
    if (l == r) {
        // 叶子节点：区间长度为离散化后相邻y坐标的差值
        mncnt[k] = 0;
        appcnt[k] = totl[k] = lft[k] = rgt[k] = seg[k] = x[l+1] - x[l];
        mnl[k] = mxl[k] = 0;
    } else {
        // 递归构建左右子树
        int mid = (l + r) >> 1;
        build(k*2, l, mid, x);
        build(k*2+1, mid+1, r, x);
        pushup(k);  // 合并子节点信息
    }
}

扫描线处理

for (int i = 1; i <= lenx; i++) {
    // 处理当前x坐标的所有矩形起始边
    for (auto j : upds[i]) {
        update(1, 1, len-1, j.first, j.second, xs[i], 1);
    }
    
    // 处理当前x坐标的所有矩形结束边  
    for (auto j : dels[i]) {
        update(1, 1, len-1, j.first, j.second, -1, -1);
    }
    
    // 查询当前有效的水平线段
    query(1, 1, len-1, xs[i], ys);
    
    // 清理标记
    for (auto j : dels[i]) {
        update(1, 1, len-1, j.first, j.second, 0, 0);
    }
}

有效线段识别

在查询过程中，当发现覆盖次数为0的连续段时：

• 这些段对应有效的水平线段 $(x_1, x_2, y)$
• 其中 $x_1$ 和 $x_2$ 由线段树节点维护的边界信息确定
• 统计出现次数和最大连续长度

复杂度分析

• 时间复杂度：$O(N \log N)$，其中 $N$ 是所有测试用例中矩形数量的总和
• 空间复杂度：$O(N)$，用于存储离散化坐标和线段树

样例解析

以第一组样例为例：

2
2 2 3 3
3 3 4 4

种植区形成的有效水平线段：

• $(2,3,2)$：在y=2行，区间[2,3]被覆盖，且左右相邻点未被覆盖
• $(2,4,3)$：在y=3行
• $(3,4,4)$：在y=4行

因此输出3个不同的 $(x_1,x_2)$ 对，每个出现1次，最大连续长度1。

总结

本题通过扫描线算法结合线段树维护y轴覆盖情况，高效地统计了所有满足条件的水平线段。关键点在于：

1. 利用离散化处理大坐标范围
2. 线段树维护覆盖信息和连续段特性
3. 扫描线按x坐标顺序处理矩形边界
4. 在覆盖次数变化时识别有效的水平线段

该算法能够处理 $N \leq 2 \times 10^5$ 的大规模数据，在时间和空间复杂度上达到最优。