C++差分数组实现区间砍树问题

根据题意，我们需要对 n 棵树进行 q 次区间砍伐操作，每次砍掉 [L, R] 区间内的树。最后统计剩余多少棵树。 一个高效的做法是使用**差分数组**或**线段树**记录每个位置被砍的次数，最后统计未被砍过的位置数量。这里直接使用布尔数组标记 + 区间覆盖模拟复杂度为 O(n*q) 可能超时，因此推荐使用**区间合并**或**差分 + 前缀和**。 思路： - 初始化一个长度为 n+2 的标记数组，初始为 false（表示树还在）。 - 对每次操作区间 [L,R]，将标记设为 true（被砍）。 - 最后统计标记为 false 的数量。 - 为了优化区间赋值，可以使用差分（快速标记区间），然后做前缀和还原。 ## 差分 + 前缀和实现 O(n+q) ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; // 差分数组，长度 n+2，避免越界 vector<int> diff(n + 2, 0); for (int i = 0; i < q; i++) { int L, R; cin >> L >> R; // 区间 [L, R] 被砍，标记为 1 diff[L] += 1; diff[R + 1] -= 1; } int remaining = 0; int current = 0; for (int i = 1; i <= n; i++) { current += diff[i]; if (current == 0) { remaining++; } } cout << remaining << endl; return 0; } ``` ## 代码说明 - 差分数组 diff 用于记录区间操作，每次区间 [L,R] 被砍，则 diff[L]++、diff[R+1]--。 - 循环 i 从 1 到 n，累加 current 得到当前树是否被砍（current > 0 表示被砍过）。 - current == 0 表示该位置从未被任何操作覆盖，树存活。 - 输出剩余存活树木数量。 例如输入： ``` 5 3 1 3 5 5 2 3 ``` 处理过程： - diff[1]++, diff[4]-- 表示 [1,3] 被砍 - diff[5]++, diff[6]-- 表示 [5,5] 被砍 - diff[2]++, diff[4]-- 表示 [2,3] 被砍 最终 current： - i=1: current=1 -> 被砍 - i=2: current=2 -> 被砍 - i=3: current=2 -> 被砍 - i=4: current=0 -> 剩余 - i=5: current=1 -> 被砍 剩余 1 棵树（位置4），输出 1。 ######[AI问答 | 668点数解答 | 2026-06-14 10:18:36]