题意：有2行，每行\(n\)个点，给你\(m\)个连接上下两行的边，问你最对能选多少条边，这些边互不相交。

题解：先固定选上面或者下面一行作为起点去遍历，假设选下面一行，我们从头开始遍历，假设遍历到\(i\)个点时，枚举它的所有出边\(to\)，假设这条边的终点为\(j\)，设\(dp[j]\)表示区间\([1,j]\)的最多方案数，那么当前的状态一定为\(dp[j]=max(dp[j],dp[j-1]+1\))，因为\(dp\)数组表示的是区间最大值，所以可以用线段树来写，简单易懂。举个例子吧，比如有\(10\)个点，我们在\(dp[5]\)的位置更新了最大值，下一个位置是\(8\)，我们要看\(dp[7]\)的值，但这\([6,7]\)这一段是空的，我们无法更新\(dp[8]\)的值，因为此时我们要看区间\([1,7]\)的最大值，这很明显是线段树嘛。。。。

代码：

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define db double
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

int n,m;
PII pt[N];
int dp[N];
vector<int> edge[N];
struct tree { int l, r, dat; }t[N << 4];

inline int ls(int p) { return p << 1; }
inline int rs(int p) { return ((p << 1) | 1); }

inline void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].dat = dp[l]; return ; }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    t[p].dat = max(t[ls(p)].dat, t[rs(p)].dat);
}

inline void change(int p, int x, int v) {
    if (t[p].l == t[p].r) { t[p].dat = v; return ; }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) change(ls(p), x, v);
    else change(rs(p), x, v);
    t[p].dat = max(t[ls(p)].dat, t[rs(p)].dat);
}


inline int ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;
    int mid = (t[p].l + t[p].r) >> 1;
    int val = -INF;
    if (l <= mid) val = max(val, ask(ls(p), l, r));
    if (r > mid) val = max(val, ask(rs(p), l, r));
    return val;
}

int main() {
    scanf("%d %d",&n,&m);
    build(1,0,N);
    for(int i=1;i<=m;++i){
        scanf("%d %d",&pt[i].fi,&pt[i].se);
        edge[pt[i].fi].pb(pt[i].se);
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        sort(edge[i].begin(),edge[i].end(),greater<int>());
        for(auto to:edge[i]){
            int now=ask(1,0,to-1);
            if(now+1>dp[to]){
                dp[to]=now+1;
                change(1,to,now+1);
            }
            ans=max(ans,dp[to]);
        }
    }
    printf("%d\n",ans);
    return 0;
}