[题解]CF1401E.Divide Square(codeforces 05)
题目描述
There is a square of size 106×106106×106 on the coordinate plane with four points (0,0)(0,0) , (0,106)(0,106) , (106,0)(106,0) , and (106,106)(106,106) as its vertices.
You are going to draw segments on the plane. All segments are either horizontal or vertical and intersect with at least one side of the square.
Now you are wondering how many pieces this square divides into after drawing all segments. Write a program calculating the number of pieces of the square.
输入格式
The first line contains two integers 𝑛n and 𝑚m ( 0≤𝑛,𝑚≤1050≤n,m≤105 ) — the number of horizontal segments and the number of vertical segments.
The next 𝑛n lines contain descriptions of the horizontal segments. The 𝑖i -th line contains three integers 𝑦𝑖yi , 𝑙𝑥𝑖lxi and 𝑟𝑥𝑖rxi ( 0<𝑦𝑖<1060<yi<106 ; 0≤𝑙𝑥𝑖<𝑟𝑥𝑖≤1060≤lxi<rxi≤106 ), which means the segment connects (𝑙𝑥𝑖,𝑦𝑖)(lxi,yi) and (𝑟𝑥𝑖,𝑦𝑖)(rxi,yi) .
The next 𝑚m lines contain descriptions of the vertical segments. The 𝑖i -th line contains three integers 𝑥𝑖xi , 𝑙𝑦𝑖lyi and 𝑟𝑦𝑖ryi ( 0<𝑥𝑖<1060<xi<106 ; 0≤𝑙𝑦𝑖<𝑟𝑦𝑖≤1060≤lyi<ryi≤106 ), which means the segment connects (𝑥𝑖,𝑙𝑦𝑖)(xi,lyi) and (𝑥𝑖,𝑟𝑦𝑖)(xi,ryi) .
It's guaranteed that there are no two segments on the same line, and each segment intersects with at least one of square's sides.
输出格式
Print the number of pieces the square is divided into after drawing all the segments.
输入输出样例
-
输入#1
复制3 3 2 3 1000000 4 0 4 3 0 1000000 4 0 1 2 0 5 3 1 1000000
输出#1
复制7
说明/提示
The sample is like this:
这个问题实际上是在考察我们如何有效地处理线段覆盖以及段分割的区域数量。下面是一些解题的思路和步骤：
步骤一：理解题意
首先，我们需要理解题目要求的是在给定一系列水平和垂直线段后，整个正方形被分成了多少个部分。每个线段都在正方形内部或与其边界相交，并且没有两条线段在同一水平线上或同一垂直线上。
步骤二：分析关键数据结构
- 水平线段列表：存储所有水平线段的信息，即它们的高度和左右端点位置。
- 垂直线段列表：存储所有垂直线段的信息，即它们的位置和上下端点位置。
步骤三：预处理
对水平线段和垂直线段进行排序，这样可以方便后续的处理。排序的关键在于水平线段按高度排序，而垂直线段按位置排序。
步骤四：构建扫描线算法
我们可以使用扫描线算法来解决这个问题。具体来说，我们可以在水平方向上“扫描”整个正方形，每次遇到一个水平线段时，就检查它与当前已知的所有垂直线段的交点。这个过程可以使用一个平衡树（例如红黑树或AVL树）来存储当前扫描线上所有的垂直线段的交点，这使得我们能够快速地找到新的交点并更新结果。
步骤五：计算分割区域的数量
每当我们遇到一个新的水平线段时，通过比较相邻两个交点之间的距离，我们可以确定新增加了多少个区域。这是因为每个新的交点都会在之前存在的区域内添加至少一个新区域。我们可以通过平衡树来维护这些信息，从而高效地计算出最终的区域步骤六：实现细节
- 在实现过程中，需要特别注意边界条件的处理，比如当扫描线遇到正方形的边界时应该如何处理。
- 考虑到输入，优化数据结构的选择和操作效率至关重要。
总结
这个问题是一个典型的扫描线算法的应用场景，通过有效的数据结构和算法设计，我们可以将复杂的问题简化为一系列更小的子问题。希望这些思路能帮助你开始解决这个问题，记住，在实际编码时，一步步调试和测试你的代码是非常你发现并修正潜在的错误。
代码优化点
-
分离关注点：将输入读取、数据处理和输出结果分开，增加代码的可读性和可维护性。
-
避免重复计算：在处理竖向线段时，直接计算贡献而不是逐个查询树状数组。
-
使用更现代的 C++ 特性：如
std::vector和std::map来代替部分静态数组，这可以减少代码量并提供更好的安全性。
优化后的代码示例
#include <bits/stdc++.h>
using namespace std;const int MAXN = 1e6 + 5;
const int B = 1e6;struct BinaryIndexTree {vector<int> c;inline int) { return x & (-x); }inline void modify(int x, int d) {for (; x < c.size(); x += lowbit(x)) c[x] += d;}inline int query(int x) {int ans = 0;for (; x; x -= lowbit(x)) ans += c[x];return ans;}
};struct Node {int x, y, d;bool operator < (const Node& rhs) const { return x < rhs.x; }
};struct vLine {int x, l, r;bool operator < (const vLine& rhs) const { return x < rhs.x; }
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<Node> seq;vector<vLine> vln;vector<int> yCoords;for (int i = 0; i < n; ++i) {int y, l, r;cin >> y >> l >> r;if (l == 0 && r == B) ++n; // Adjusting initial regions countseq.emplace_back(l, y, 1);seq.emplace_back(r + 1, y, -1);yCoords.push_back(y);}for (int i = 0; i < m; ++i) {int x, l, r;cin >> x >> l >> r;if (l == 0 && r == B) ++n;v, l, r);}sort(begin(seq), end(seq));sort(begin(vln), end(vln));BinaryIndexTree bit;bit.c.resize(MAXN);int j = 0;long long ans = n;for (const auto& vl : vln) {while (j < seq.size() && seq[j].x <= vl.x) {++j;bit.modify(seq[j].y + 1, seq[j].d);}ans += bit.query(vl.r + 1) - bit.query }cout << ans << '\n';return 0;
}
解释
- 使用
std::vector替代了静态数组，提供了动态分配内存的能力，并简化了数组操作。 - 使用
std::cin和std::cout替换了scanf和printf，虽然这在性能上可能有轻微的影响，但增加了代码的可读性和现代感。 - 将树状数组的大小动态分配，避免了硬编码的上限。
这些改动没有改变算法的核心逻辑，而是提高了代码的质量和可维护性。