题解区里全用的线段树……

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define INT_MAX 2000000000
int f[50005],own[50005],r[50005],v[50005],l[50005];
inline int query(int x,int y){
	int i,ret=INT_MAX;
	if(own[x]==own[y])
		for(i=x;i<=y;++i)
			ret=std::min(ret,f[i]);
	else{
		for(i=x;i<=r[own[x]];++i)
			ret=std::min(ret,f[i]);
		for(i=l[own[y]];i<=y;++i)
			ret=std::min(ret,f[i]);
		for(i=own[x]+1;i<own[y];++i)
			ret=std::min(ret,v[i]);
	}
	return ret;
}
inline void remake(int id,int k){
	f[id]=k;
	int i;v[i]=INT_MAX;
	for(i=l[own[id]];i<=r[own[id]];++i)
		v[i]=std::min(v[i],f[i]);
	return;
}
int main(){int t,n,m,cnt,len,i,j,left,right;
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&m);
		memset(f,0x3f,sizeof f);
		f[1]=0;
		cnt=n/int(len=sqrt(n));
		for(i=1;i<=cnt;++i){
			l[i]=(i-1)*len+1;
			r[i]=i*len;
		}
		if(r[cnt]!=n){
			l[cnt+1]=r[cnt]+1;
			r[cnt+1]=n;
			++cnt;
		}
		for(i=1;i<=cnt;++i){
			v[i]=INT_MAX;
			for(j=l[i];j<=r[i];++j)
				own[j]=i;
		}
		v[1]=0;
		for(i=1;i<=m;++i){
			scanf("%d %d",&left,&right);
			remake(right,query(left,right-1)+1);
		}
		printf("%d\n",f[n]);
	}
	return 0;
}

方程是 $f_i=1+\max\limits_{l_i}^{r_i-1}\{f_j\}$，应该没问题。

分块哪里挂了