单调队列DP/差分约束
差分约束会TLE
#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f,N=1000010;
int n,m,l[N],r[N],q[N],f[N];
void read(int &x){
x=0;int f=1;char c=getchar();
while(!isdigit(c)){ if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){ x=x*10+c-'0';c=getchar();}
x*=f;
}
void gmin(int &x,const int &y){ x=x<y?x:y; }
void gmax(int &x,const int &y){ x=x>y?x:y; }
int main(){
//freopen("input.txt","r",stdin);
read(n),read(m);
go(i,1,n+1) r[i]=i-1;
int a,b;
go(i,1,m){
read(a),read(b);
gmax(l[b+1],a);//虽然>b+1的也可以更新,但我们选择更有代表性的b+1
gmin(r[b],a-1);//虽然<b的的也可以更新,但我们选择更有代表性的b
}
go(i,2,n+1) gmax(l[i],l[i-1]);
com(i,n,1) gmin(r[i],r[i+1]);
//注意!l[i],r[i]单调递增,f[i]要尽可能大(其实可以用线段树?)
//若x<y&&f[x]<=f[y],则x无用
int L=1,R=1,j=0;
q[1]=0;//初状态为f[0]哇!
go(i,1,n+1){
while(j<r[i]&&j++<n){
if(f[j]==-1) continue;
while(L<=R&&f[q[R]]<f[j]) --R;
q[++R]=j;
}
while(L<=R&&q[L]<l[i]) ++L;
if(L>R) f[i]=-1;
else f[i]=f[q[L]]+(i!=n+1?1:0);
}
printf("%d",f[n+1]);
return 0;
}