吐槽

看这道题的时候，由于英语太菜
读题读了好久都没读懂
依据暂时的理解打了一个程序之后发现一直WA
最后在玄学注释（去掉排序）程序的时候，居然A了。。。
之后在机房英语巨佬シンドリー的帮助下才懂得了题意。。。

分析

不太懂题意的，可以看看这位巨佬的Blog
一眼题？（以前在Atcoder上边好像做过类似的题）
我们需要的是按照题目给定的序列顺序找出其中的几段
能够使得每两端之间有至少一个交点的情况下覆盖整段序列
我们设DP[i]表示覆盖完所需要的最小段数
所以我们可以得到DP方程

发现，这个状态转移是一个区间最小值的转移
所以我们直接上线段树优化DP即可

代码

//POJ 1769
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxM=5e5+10;

LL Total,Range;
struct Node {
    LL From,To;
    friend bool operator < (Node A,Node B) {
        if(A.To!=B.To) return A.To<B.To;
        else return A.From<B.From;
    }
}Line[MaxM];
LL DP[MaxM],Loc,Max;
LL Min[MaxM<<2];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Push_up(LL X) { Min[X]=min(Min[Lson],Min[Rson]); }
inline void Update(LL X,LL L,LL R,LL Loc,LL Temp) {
    if(L==R) { Min[X]=min(Min[X],Temp); return; }
    LL Mid=(L+R)>>1;
    if(Loc<=Mid) { Update(Lson,L,Mid,Loc,Temp); }
    else { Update(Rson,Mid+1,R,Loc,Temp); }
    Push_up(X);
}

inline LL Get(LL X,LL L,LL R,LL From,LL To) {
    if(L>=From && R<=To) { return Min[X]; }
    LL Mid=(L+R)>>1,Res=INF;
    if(From<=Mid) { Res=min(Res,Get(Lson,L,Mid,From,To)); }
    if(To>Mid) { Res=min(Res,Get(Rson,Mid+1,R,From,To)); }
    Push_up(X);
    return Res;
}

signed main() {
    // File();
    // ios::sync_with_stdio(false);
    scanf("%lld %lld",&Total,&Range);
    // cin>>Total>>Range;
    Cl(Min,0x3f); Cl(DP,0x3f);          
    FOR(i,1,Range) scanf("%lld %lld",&Line[i].From,&Line[i].To);
    // sort(Line+1,Line+Range+1);
    Update(1,1,Total,1,0);  
    FOR(i,1,Range) {
        LL Temp=Get(1,1,Total,Line[i].From,Line[i].To-1);
        DP[Line[i].To]=min(DP[Line[i].To],Temp+1);
        Update(1,1,Total,Line[i].To,DP[Line[i].To]);
    }
    cout<<Get(1,1,Total,Total,Total)<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}