setで範囲を管理

setで範囲を管理できます。
範囲の重複をどのように考えるかでコードが異なります。
l=0,r=1とl=2,r=3を結合と考えると以下のようなコードになります。
結合されると範囲はl=0,r=3となります。
結合の条件を変えたい場合はコードを書き換えてください。

#define INF 1000000000000LL

ll q;
cin>>q;
set< pair<ll, ll> > se;
se.insert(mp(-INF, -INF));
se.insert(mp(INF, INF));

for(int i = 0; i < q; i++){
  ll l,r;
  cin>>l>>r;
  se.insert(mp(l,r));
  set< pair<ll, ll> >::iterator itr = se.lower_bound(mp(l, -1));
  itr--;
  // connect left
  if(l-1 <= itr->second) l = itr->first;
  else itr++;
  // connect right
  while(r+1 >= itr->first){
    r = max(r, itr->second);
    se.erase(itr++);
  }
  se.insert(mp(l,r));
}