很神仙的dp...假装自己看懂了，以后回来复习复习...
设$f_{i}$表示从$1$到$i$，且$i$这个点必放的最大数量。
一个区间有两个限制条件：至少放一个，至多放一个。
因为一个区间至多要放一个，所以所有包含这个点的区间都不能再放，设$r_{i}$表示包含这个点的区间中最小的左端点$ - 1$。
因为一个区间至少要放一个，所以不能有区间中一个都不放，设$l_{i}$表示整个区间在当前点之前的最大的左端点。
这样子就有了转移方程：$f_{i} = max(f_{j}) + 1$ $(l_{i} \leq j \leq r_{i})$。
弄一个单调队列优化。
读入的时候读入了$x$和$y$，用$x - 1$更新$r_{y}$，用$x$更新$l_{y + 1}$。
有一点问题就是可能会出现$l$不严格不下降，$r$不严格不上升的情况，考虑到$l$, $r$的现实意义，所以处理完读入的时候扫一遍处理一下。
细节：
1、因为$f$表示必选的情况，那么可以让$f_{n + 1}$参与转移，如果$f_{n + 1}$合法，那么最后答案就是$f_{n + 1} - 1$。（我就是这样WA1次的）
2、把不合法的状态标记为$-1$，注意不合法的状态不参与转移。（我就是这样又WA了一次）
还是太菜了。
时间复杂度$O(n)$。
Code：
#include <cstdio>
#include <cstring>
using namespace std;; const int N = 2e5 + ; int n, m, ln[N], rn[N], q[N], f[N]; inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > ''|| ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline void chkMax(int &x, int y) {
if(y > x) x = y;
} inline void chkMin(int &x, int y) {
if(y < x) x = y;
} int main() {
// freopen("testdata.in", "r", stdin); read(n), read(m);
for(int i = ; i <= n + ; i++) rn[i] = i - ;
for(int x, y, i = ; i <= m; i++) {
read(x), read(y);
chkMin(rn[y], x - );
chkMax(ln[y + ], x);
} for(int i = n; i >= ; i--) chkMin(rn[i], rn[i + ]);
for(int i = ; i <= n; i++) chkMax(ln[i], ln[i - ]); int l = , r = , pos = ; q[] = ;
for(int i = ; i <= n + ; i++) {
for(; l <= r && q[l] < ln[i]; ++l);
if(l <= r) f[i] = f[q[l]] + ;
else f[i] = -;
for(; pos <= rn[i + ]; ++pos) {
if(f[pos] == -) continue;
for(; l <= r && f[q[l]] < f[pos]; --r);
q[++r] = pos;
}
} if(f[n + ] != -) f[n + ]--;
printf("%d\n", f[n + ]);
return ;
}