\(2 \times 10^5\) 程度の要素の数列 \(X = (x_1,\ldots,x_N)\) に対するLISは以下のように求められます(後の解法に続けるためによくある \(\mathrm{dp}\) 配列等の定義から細部を調整しています)。

• \(1 \leq i \leq N\) に対し、\(\mathrm{dp}_i\) を長さ \(i\) の単調増加列の末尾の要素の最小値(存在しない場合は \(\mathrm{Inf}\) ) とし、すべて \(\mathrm{Inf}\) で初期化。
• \(i=1,2,\ldots,N\) の順に、\(\mathrm{dp_j} \geq x_i\) であるような最小の \(j\) を二分探索で求め、\(\mathrm{dp_j}\) を \(x_i\) で更新する。
• 最終的に \(\mathrm{dp_i} \neq \mathrm{Inf}\) となる \(i\) の個数が答え。

これを本問に適用します。サイズ \(10^9\) の \(01\) 列であって、\(\mathrm{dp}_i =x \) なる \(i\) が存在するならば \(x\) 番目の値が \(1\)、そうでなければ \(0\) であるようなものを考えます。すると、\((l_i,r_i)\) に対応する処理は、番号が \(l_i\) 以上の \(1\) を番号が小さい方から高々 \(r_i-l_i+1\) 個 \(0\) にし、\(l_i\) 番目から \(r_i\) 番目までを \(1\) にするという操作になります。これは座標圧縮をした上で区間更新・区間加算の遅延セグ木を使うことで全体で \(\mathrm{O}(N \log N)\) でシミュレーション可能です。
あるいは、\(\mathrm{dp}\) 配列上で値が \(5,6,7,\ldots\) と \(1\) ずつ増えていく区間をmapで管理する方法でも十分高速に答えを求められます(「区間を管理」等で調べると資料が見つかります)。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace atcoder;
using namespace std;

pair<int,int> op(pair<int,int> a,pair<int,int> b){
	a.first += b.first;
	a.second += b.second;
	return a;
}

pair<int,int> e(){
	return make_pair(0,0);
}

pair<int,int> mapping(int a,pair<int,int> b){
	if(a==-1)return b;
	b.first = b.second * a;
	return b;
}

int composition(int a,int b){
	if(a==-1)return b;
	return a;
}

int id(){
	return -1;
}

int X;
bool f(pair<int,int> x){
	return x.first<=X;
}

int main() {
	
	int N;
	cin>>N;
	
	vector<int> l(N),r(N);
	vector<int> t;
	for(int i=0;i<N;i++){
		cin>>l[i]>>r[i];
		r[i]++;
		t.push_back(l[i]);
		t.push_back(r[i]);
	}
	
	sort(t.begin(),t.end());
	t.erase(unique(t.begin(),t.end()),t.end());
	
	vector<pair<int,int>> temp;
	for(int i=0;i<t.size()-1;i++){
		temp.emplace_back(0,t[i+1]-t[i]);
	}
    
	lazy_segtree<pair<int,int>,op,e,int,mapping,composition,id> seg(temp);
	
	for(int i=0;i<N;i++){
		int il = distance(t.begin(),lower_bound(t.begin(),t.end(),l[i]));
		int ir = distance(t.begin(),lower_bound(t.begin(),t.end(),r[i]));
		X = r[i]-l[i];
		
		int rr = seg.max_right<f>(il);
		X -= seg.prod(il,rr).first;
		seg.apply(il,rr,0);
		
		if(rr!=temp.size()){
			auto g = seg.get(rr);
			g.first -= X;
			seg.set(rr,g);
		}
		
		seg.apply(il,ir,1);
	}
	
	cout<<seg.all_prod().first<<endl;
	
    return 0;
}