题意
有$n$头奶牛，$m$条约束$(a_i,b_i)$，表示$a_i$到$b_i$间有且仅有一头带斑点的奶牛，求最多可能有多少只斑点奶牛
数据范围：$1 \le n \le 200000,1 \le m \le 100000$
题解
将有且仅有一头拆解为至多一头+至少一头
初步思路为差分约束，但明显复杂度过高
发现可以$dp$，用$f[i]$表示第$i$头奶牛有斑点的情况下前$i$头奶牛最多有多少斑点，易得状态转移方程$$f[i]=max(f[j]+1)$$其中$j < i$且满足上述约束
现在思考如何找到所有满足约束的$j$
由每个区间最多有一个斑点，不能放在包含$i$的区间里，需要记录所有包含$i$的区间的$l$的最小值$r[i]$，$j \le r[i]$
由每个区间最少有一个斑点，小于$i$且不包含$i$的区间中要放一个，需要记录所有不包含$i$的区间的$l$的最大值$l[i]$，$j \ge l[i]$
$dp$时$j$的取值范围为$[l[i],r[i]]$
读入$(a_i,b_i)$时，用$a_i-1$更新$r[b_i]$，用$a_i$更新$l[b_i+1]$
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
r[b]=min(r[b],a-1);
l[b+1]=max(l[b+1],a);
}发现状态转移方程只与$j$有关，可以使用单调队列优化
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200000+10;
int n,m,a,b;
int h,t;
int l[N],r[N],q[N],dp[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n+1;i++)
r[i]=i-1;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
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]);
q[h=t=1]=0;
for(int i=1,j=1;i<=n+1;i++){
for(;j<=r[i] && j<=n;j++){
if(dp[j]==-1)
continue;
for(;h<=t && dp[j]>dp[q[t]];t--);
q[++t]=j;
}
for(;h<=t && q[h]<l[i];h++);
if(h<=t)
dp[i]=dp[q[h]]+(i<n+1);
else dp[i]=-1;
}
printf("%d",dp[n+1]);
return 0;
}