题目大意：给一个长度为n的区间，m条线段序列，找出这个序列的一个最短子序列，使得区间完全被覆盖。
题目分析：这道题不难想，定义状态dp(i)表示用前 i 条线段覆盖区间1~第 i 线段的右端点需要的最少数目，状态转移方程为dp(i)=min(dp(j))+1。其中第 j 条线段与第 i 条线段有交集。很显然，这个状态转移方程跟LIS问题的状态转移方程几乎一样，时间复杂度为O(m*m)。起初，我想套用LIS问题的O(nlogn)的那种解法，得到两个WA之后才感觉到很难套用成功，理论上完全没问题，但实现起来很困难。之后查了题解才知道，是用线段树优化的。
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; const int N=50005;
const int INF=1000000000; int n,m;
int tr[N*4]; void build(int rt,int l,int r)
{
tr[rt]=INF;
if(l==r) return ;
build(rt<<1,l,(l+r)/2);
build(rt<<1|1,(l+r)/2+1,r);
} void update(int pos,int rt,int val,int l,int r)
{
if(tr[rt]>val) tr[rt]=val;
if(l==r) return ;
int m=(l+r)>>1;
if(pos<=m) update(pos,rt<<1,val,l,m);
else update(pos,rt<<1|1,val,m+1,r);
} int query(int rt,int L,int R,int l,int r)
{
if(L<=l&&r<=R) return tr[rt];
int m=(l+r)>>1;
if(R<=m) return query(rt<<1,L,R,l,m);
else if(L>m) return query(rt<<1|1,L,R,m+1,r);
else return min(query(rt<<1,L,R,l,m),query(rt<<1|1,L,R,m+1,r));
} int main()
{
int a,b,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
build(1,1,n);
update(1,1,0,1,n);
while(m--){
scanf("%d%d",&a,&b);
int x=query(1,a,b,1,n);
update(b,1,x+1,1,n);
}
printf("%d\n",query(1,n,n,1,n));
if(T) printf("\n");
}
return 0;
}