题目大概就是要，给一个由若干区间[Si,Ti]组成的序列，求最小长度的子序列，使这个子序列覆盖1到n这n个点。
- dp[i]表示从第0个到第i个区间且使用第i个区间，覆盖1到Ti所需的最少长度
- 对于Si=1的i区间dp值就是1了，要求的答案就是所有Ti=n的最小的dp值
转移就是，dp[i]=dp[j]+1，Si<=Tj<=Ti。不过枚举转移这样显然会T的，可以转化成RMQ来提升效率，用线段树成段更新成段查询即可，即维护1...n的覆盖所需区间的最小值，这样时间复杂度O(mlogn)。
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 55555 inline int min(int a,int b){
if(a==) return b;
if(b==) return a;
if(a<b) return a;
return b;
} int tree[MAXN<<],tag[MAXN<<],N,x,y,z;
void update(int i,int j,int k){
if(x<=i && j<=y){
tree[k]=min(tree[k],z);
tag[k]=min(tag[k],z);
return;
}
if(tag[k]){
tree[k<<]=min(tree[k<<],tag[k]);
tree[k<<|]=min(tree[k<<|],tag[k]);
tag[k<<]=min(tag[k<<],tag[k]);
tag[k<<|]=min(tag[k<<|],tag[k]);
tag[k]=;
}
int mid=i+j>>;
if(x<=mid) update(i,mid,k<<);
if(y>mid) update(mid+,j,k<<|);
tree[k]=min(tree[k<<],tree[k<<|]);
}
int query(int i,int j,int k){
if(x<=i && j<=y){
return tree[k];
}
if(tag[k]){
tree[k<<]=min(tree[k<<],tag[k]);
tree[k<<|]=min(tree[k<<|],tag[k]);
tag[k<<]=min(tag[k<<],tag[k]);
tag[k<<|]=min(tag[k<<|],tag[k]);
tag[k]=;
}
int mid=i+j>>,res=;
if(x<=mid) res=min(res,query(i,mid,k<<));
if(y>mid) res=min(res,query(mid+,j,k<<|));
return res;
} int main(){
int n,m,a,b;
scanf("%d%d",&n,&m);
for(N=; N<n; N<<=);
int ans=;
for(int i=; i<m; ++i){
scanf("%d%d",&a,&b);
int res=;
if(a==) res=;
else{
x=a; y=b;
res=query(,N,);
if(res) ++res;
}
x=; y=b; z=res;
update(,N,);
if(b==n) ans=min(ans,res);
}
printf("%d\n",ans);
return ;
}