感谢 @\(\color{#AEF}{\texttt{Celestial Cyan}}\) 大神对我的骚扰帮助。
分析
一眼 DP。
对于求最大满足条件区间数，我们定义状态函数 \(\mathit{f}_{i}\) 表示在第 \(1\) 到 \(i\) 个区间中选择，且必选第 \(i\) 个区间能够得到的最大长度。有转移方程：\(\mathit{f}_{i}=\max\{f[j]|\mathit{a}_{j}\le\mathit{a}_{i} \land \mathit{b}_{j} \ge \mathit{b}_{i} \}+1\)。
可以得到 \(50\) 分的 \(O(n^2)\) 的代码：
for(re int i=1;i<=n;++i){
f[i]=1;
for(re int j=1;j<i;++j){
if(a[i].l>=a[j].l&&a[j].r>=a[i].r){
if(f[j]+1>f[i]) f[i]=f[j]+1,nxt[i]=j;
}
}
}
考虑优化 \(\mathit{f}_{i}\) 的转移。这个代码与 LIS 模板几乎一致，所以很显然的也可以使用树状数组优化。因为我们需要记录方案，所以树状数组存 \(2\) 维：价值与该价值对应的下标。
我们将 \(\mathit{a},\mathit{b}\) 用一个结构体存放，按第一维从小到大排序。可以得到：对于每一个 \(i\)，都有 \(1 \le j \le i,\mathit{a}_j \le \mathit{a}_i\)。这样我们就消除了区间左端点的影响。剩下的就用树状数组查询 $ \ge \mathit{b}_i$ 的最大的 \({f}_j\) 的值与其下标。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second
const int N=1e5+10,MAXN=1e6+10;
int n;
PII f[N],tr[MAXN];
struct node{
int l,r;
}a[N];
stack<int> st;
int id,maxx;
il bool cmp(node a,node b){return (a.l!=b.l)?(a.l<b.l):(a.r>b.r);}
il void insert(int x,int y,int id){
while(x){
if(tr[x].x<y) tr[x].x=y,tr[x].y=id;
x-=x&(-x);
}
return ;
}
il PII query(int x){
PII ans;ans={0,0};
while(x<=MAXN){
if(ans.x<tr[x].x) ans.x=tr[x].x,ans.y=tr[x].y;
x+=x&(-x);
}
ans.x++;return ans;
}
il void read(){
scanf("%lld",&n);
for(re int i=1;i<=n;++i) scanf("%lld%lld",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
return ;
}
il void solve(){
for(re int i=1;i<=n;++i) f[i]=query(a[i].r),insert(a[i].r,f[i].x,i);
for(re int i=1;i<=n;++i){
if(maxx<f[i].x) maxx=f[i].x,id=i;
}
while(id!=0) st.push(id),id=f[id].y;
return ;
}
il void print(){
printf("%lld\n",maxx);
while(!st.empty()){
int now=st.top();st.pop();
printf("%lld %lld\n",a[now].l,a[now].r);
}
return ;
}
signed main(){
read(),solve(),print();
return 0;
}