差分,tr[i]为0则说明有树。
#include <iostream> #include <cstring> using namespace std; int tr[10010]; int main() { int l, m; memset(tr, 0, sizeof(tr)); cin >> l >> m; for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; tr[l]--; tr[r+1]++; } int cnt = 0; if (tr[0] == 0) cnt++; for (int i = 1; i <= l; i++) { tr[i] += tr[i - 1]; if (tr[i] == 0) cnt++; } cout << cnt; return 0; }