题意
有 $n(n\le 2\times 10^5)$ 头奶牛，有 $m(m\le 10^5)$ 组关系 $(l,r)$ ，表示 $[l,r]$ 奶牛中有且仅有一头有斑点。问最多有多少头奶牛有斑点。
题解
第一反应就是差分约束，不过因为是从DP点进来的所以我去看题解确认了下，得知会T（除了玄学的限定次数）。
方程式还好想，就是转移比较神奇。用 $f[i]$ 表示第 $i$ 头牛有斑点的前提下前 $i$ 头牛最多有多少有斑点。对于一些满足条件的点 $j$ ，可以得到方程：
$$f[i]=f[j]+1$$
$j$ 需要满足以下限定条件：
- $j < i$
废话 - $j$ 在所有包含 $i$ 的区间的前面（最多一个）
- 对于所有整个都在 $i$ 前面的区间，$j$ 必须在区间中（至少一个）
可以通过上面的条件预处理出满足条件的 $j$ 的区间 $[L_i,R_i]$ ，然后单调队列优化DP。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=200005;
int n,m,a,b,L[N],R[N],q[N],f[N];
signed main()
{
n=read(); m=read();
for (int i=1;i<=n+1;i++) R[i]=i-1;
for (int i=1;i<=m;i++)
{
a=read(); b=read();
R[b]=min(R[b],a-1);
L[b+1]=max(L[b+1],a);
}
for (int i=n;i;i--) R[i]=min(R[i],R[i+1]);
for (int i=2;i<=n+1;i++) L[i]=max(L[i],L[i-1]);
int l=1,r=1,j=1; q[1]=0;
for (int i=1;i<=n+1;i++)
{
int maxj=min(R[i],n);
for (;j<=maxj;j++)
{
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]=f[q[l]]+(i<=n);
else f[i]=-1;
}
return !printf("%d",f[n+1]);
}