校门外的树：C++ 区间处理与标记法实战

解法二：区间端点优化法

当区间数量较多时，可以通过排序合并来减少操作次数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int l, m;
    cin >> l >> m;
    vector<pair<int, int>> intervals;
    while (m--) {
        int u, v;
        cin >> u >> v;
        intervals.emplace_back(u, v);
    }
    // 按区间起点排序
    sort(intervals.begin(), intervals.end());
    int removed = 0;
    int last = -1;
    for (auto& interval : intervals) {
        int u = interval.first, v = interval.second;
        if (u > last) {
            removed += v - u + 1;
            last = v;
        } else if (v > last) {
            removed += v - last;
            last = v;
        }
    }
    cout << (l + 1 - removed) << endl;
    return 0;
}

代码优化与细节

空间优化技巧

如果内存紧张，可以使用 bitset 减少空间占用。

// 使用 bitset 减少空间占用
#include <bitset>
bitset<10001> trees; // 替代 vector<bool>

输入处理优化

对于大量输入，开启快速 IO 能显著提升速度。

// 快速 IO 加速
ios::sync_with_stdio(false);
cin.tie(nullptr);

复杂度分析

测试验证

易错点提醒

错误 1：数组越界

vector<bool> trees(l); // 错误：少一个元素
for (int i = 0; i <= l; ++i) // 越界访问

修正：

vector<bool> trees(l + 1);

错误 2：端点处理错误

for (int i = u; i < v; ++i) // 错误：漏掉 v 端点

修正：

for (int i = u; i <= v; ++i)

错误 3：计数错误

int count = l - removed; // 错误：忘记 +1

修正：

int count = l + 1 - removed;

经验总结

1. 问题抽象：将实际问题转化为区间处理问题。
2. 数据结构选择：根据数据范围选择合适的数据结构。
3. 边界检查：特别注意区间的端点处理。
4. 测试验证：设计多种测试案例验证算法。

拓展思考

1. 动态区间增加和查询：使用线段树数据结构，支持区间更新和区间查询。
2. 处理超大 l 值：如 1e9，可使用离散化和区间合并，减少空间使用量。
3. 求被移除次数最多的树：记录每棵树被移除的次数。

vector<int> count(l+1); // 记录每棵树被移除的次数

校门外的树问题教会我们如何用编程解决现实中的空间规划问题，是算法竞赛中经典的区间处理案例。