洛谷题目页面传送门 & CodeForces题目页面传送门
题意见洛谷里的翻译。
一脸DP的样，于是考虑DP。
与普通的LIS类似，设(dp_{i,j})表示考虑到第(i)个数，最后一位为(a_i=j)的LIS长度。显然，第二维是定义在值域(left[1,10^9 ight])上的，无论如何优化它都会出现在时间/空间复杂度上，受不起。于是考虑一种惯用套路，将DP数组的定义域和值域调换，即设(dp_{i,j})表示考虑到第(i)个数，长度为(j)的IS的最后一位最小为多少（如果无法实现则为(+infty)）。
边界为(dp_{0,i}=egin{cases}0&i=0\+infty&i>0end{cases})，目标为(maxlimits_{iin[1,n],dp_{n,i}<+infty}{i})，状态转移方程为(dp_{i,j}=minegin{cases}dp_{i-1,j}\max(l_i,dp_{i-1,j-1}+1)&dp_{i-1,j-1}<rend{cases})（显然，基于贪心，若选(a_i)，那么在可能情况下(a_i)越小越好）。这样空间复杂度可以用滚动数组压到(mathrm O(n))，但时间复杂度是(mathrm O!left(n^2 ight))的。考虑优化。
注意到转移时的最优决策只可能为(dp_{i-1,j},l_i,dp_{i-1,j-1}+1)这(3)种，于是分情况讨论：
- 转移到(l_i)。当且仅当(egin{cases}l_igeq dp_{i-1,j-1}+1\l_ileq dp_{i-1,j}end{cases})。不难发现，(forall iin[0,n])，(dp_i)不为(+infty)的那部分是严格单调上升的（易证）。于是我们设(las)为最大的(j)使得(dp_{i-1,j}<l_i)。那么(egin{cases}l_igeq dp_{i-1,j-1}+1\l_ileq dp_{i-1,j}end{cases}Rightarrowegin{cases}j-1leq las\j>lasend{cases}Rightarrow j=las+1)；
- 转移到(dp_{i-1,j-1}+1)。当且仅当(egin{cases}dp_{i-1,j-1}+1>l_i\dp_{i-1,j-1}+1leq dp_{i-1,j}\dp_{i-1,j-1}<rend{cases})（(dp_{i-1,j-1}+1=l_i)归在情况(1)里）。根据单调性，(dp_{i-1,j-1}+1leq dp_{i-1,j})显然恒成立。设(las')为最大的(j)使得(dp_{i-1,j}<r_i)。那么(egin{cases}dp_{i-1,j-1}+1>l_i\dp_{i-1,j-1}<rend{cases}Rightarrowegin{cases}j-1>las\j-1leq las'end{cases}Rightarrow jin[las+2,las'+1])；
- 转移到(dp_{i-1,j})。不满足情况(1,2)的条件则为此情况。
我们可以维护(dp_i)这个数列，每此转移即令(dp_i=dp_{i+1})。不难发现，这样想的话，情况(3)相当于什么也不做，正好我们也没分析情况(3)的充要条件，于是只需要考虑支持情况(1,2)对应的操作即可。不难想到可以用平衡树维护，这里使用fhq-Treap。情况(1)就是个单点修改；情况(2)可以转化为剖出区间([las+1,las'])后，删除第(las'+1)个元素并将第(las+1)个元素在原位拷贝一份，然后区间增加(1)。与情况(2)一综合，可以把“单点修改、将第(las+1)个元素在原位拷贝一份”简化成“在第(las+1)个元素的位置添加”（当然不简化也没关系）。这里面涉及到删除操作，由于本憨憨不想算总共会新建多少个节点，而且正好找个机会练习一下，于是采用垃圾回收，显然任意时刻元素数(leq|[0,n]|=n+1)。
时间复杂度(mathrm O(nlog n))，空间复杂度(mathrm O(n))。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define X first
#define Y second
const int inf=0x3f3f3f3f;
mt19937 rng(20060617/*信仰优化*/);
const int N=300000;
int n;//数的数量
int l[N+1],r[N+1];//限制区间
struct fhq_treap{//fhq-Treap
int sz/*点数*/,root/*根*/;
struct node{unsigned key;int lson,rson,sz,v,lz;}nd[N+2];
#define key(p) nd[p].key
#define lson(p) nd[p].lson
#define rson(p) nd[p].rson
#define sz(p) nd[p].sz
#define v(p) nd[p].v
#define lz(p) nd[p].lz
stack<int> rub;//垃圾栈
void recyc(int p){rub.push(p);}//垃圾回收
int nwnd(int v){//新建节点
int p;
if(rub.size())p=rub.top(),rub.pop();//垃圾再利用
else p=++sz;
return nd[p]=node({rng(),0,0,1,v,0}),p;
}
void sprup(int p){sz(p)=sz(lson(p))+1+sz(rson(p));}//上传
void sprdwn(int p){//下传
if(lz(p)){
v(lson(p))+=lz(p);v(rson(p))+=lz(p);
lz(lson(p))+=lz(p);lz(rson(p))+=lz(p);
lz(p)=0;
}
}
int bld(int l=0,int r=n){//建树
int mid=l+r>>1,p=nwnd(mid?inf:0);
if(l<=mid-1)lson(p)=bld(l,mid-1);
if(mid+1<=r)rson(p)=bld(mid+1,r);
return sprup(p),p;
}
void init(){//fhq-Treap初始化
nd[sz=0]=node({0,0,0,0,0,0});
root=bld();
}
pair<int,int> split(int x,int p=-1){~p||(p=root);
if(!x)return mp(0,p);
pair<int,int> sp;
sprdwn(p);
if(x<=sz(lson(p)))return sp=split(x,lson(p)),lson(p)=sp.Y,sprup(p),mp(sp.X,p);
return sp=split(x-sz(lson(p))-1,rson(p)),rson(p)=sp.X,sprup(p),mp(p,sp.Y);
}
int mrg(int p,int q){
if(!p||!q)return p|q;
sprdwn(p);sprdwn(q);
if(key(p)<key(q))return rson(p)=mrg(rson(p),q),sprup(p),p;
return lson(q)=mrg(p,lson(q)),sprup(q),q;
}
int lss(int v,int p=-1)/*以p为根的子树内<v的数的数量*/{~p||(p=root);
if(!p)return 0;
sprdwn(p);
if(v(p)<v)return sz(lson(p))+1+lss(v,rson(p));
return lss(v,lson(p));
}
void trs(int x){//转移
pair<int,int> sp=split(lss(l[x]));
if(!sp.Y)return;
pair<int,int> sp0=split(lss(r[x],sp.Y),sp.Y);
if(sp0.Y){
pair<int,int> sp1=split(1,sp0.Y);
recyc(sp1.X);//删除并回收
v(sp0.X)++;lz(sp0.X)++;//区间增加
root=mrg(mrg(mrg(sp.X,nwnd(l[x])/*添加*/),sp0.X),sp1.Y);
}
else{
pair<int,int> sp1=split(sz(sp0.X)-1,sp0.X);
recyc(sp1.Y);//删除并回收
v(sp1.X)++;lz(sp1.X)++;//区间增加
root=mrg(mrg(sp.X,nwnd(l[x])/*添加*/),sp1.X);
}
}
int at(int x,int p=-1)/*第x个元素（0-indexed）*/{~p||(p=root);
sprdwn(p);
if(sz(lson(p))+1==x+1)return v(p);
if(sz(lson(p))>=x+1)return at(x,lson(p));
return at(x-sz(lson(p))-1,rson(p));
}
void dfs(int p=-1)/*调试用*/{~p||(p=root);
if(!p)return;
sprdwn(p);
dfs(lson(p));
cout<<v(p)<<" ";
dfs(rson(p));
}
}dp;//当前的DP数组
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
dp.init();//fhq-Treap初始化
for(int i=1;i<=n;i++)dp.trs(i)/*,dp.dfs(),puts("")*/;//转移
// for(int i=0;i<=n;i++)cout<<dp.at(i)<<" ";puts("");
for(int i=n;;i--)if(dp.at(i)<inf)return cout<<i,0;//计算答案
return 0;
}