校门外的树(hard)

之前一直没有想到该怎么去写 面对1e9的长度束手无策
刚刚听课的时候 反反复复听到区间二字
一个奇妙的想法就出现在我的脑中
既然一棵树只能被拔掉一次 那么我只需要将所有区间合并
设区间 [l[i], r[i]], 那么拔掉的树的颗数即为r[i] - l[i] + 1
对拔掉树的所有区间求和得到拔树的总和为sum 剩下树的棵数即为l - sum + 1

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
int main ()
{
  ios::sync_with_stdio(0), cin.tie(0);
  vector<pi> a;
  int l, n;cin >> l >> n;
  for (int i = 1;i <= n ;++ i)
  {
    int l, r;cin >> l >> r;
    a.push_back({l, r});
  }
  
  auto merge = [&](vector<pi> &segs) -> void
  {
    vector<pi> res;
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for (auto i : segs)
    {
      if (ed < i.first)
      {
        if (st != -2e9) res.push_back({st, ed});
        st = i.first, ed = i.second;
      }
      else ed = max(ed, i.second);
    }
    if (st != -2e9) res.push_back({st, ed});
    segs = res;
  };
  
  merge(a);
  int ans = 0;
  for (auto i : a)
  {
    //cout << i.first;
    ans += i.second - i.first + 1;
  }
  cout << l - ans + 1 << '\n';
}