分类： USACO

传说这一题可以用差分约束，不过我个人的第一眼想法是\(DP\)。
首先我们令\(f_{i}\)为，第\(i\)个奶牛有斑点，\(DP\)到第\(i\)个奶牛，此时最多有多少只奶牛。
我们可以发现两点：一个区间最多有1个有斑点的奶牛，且一个区间最少有1个有斑点的奶牛。
对于当前的点，我们很容易可以知道，所有覆盖当前点的区间，在其他的地方都不能有有斑点的奶牛。
这也就等价于，转移是必须从包含\(f_{i}\)的所有区间中的左端点的最小值开始转移的。
与此同时，我们还必须明白，因为每个区间最少有一个有斑点的奶牛，因而为了保证满足提议，转移点到\(f_{i}\)之间的所有区间不能有空的。
这也就等价于，所有不包含\(f_{i}\)（当然显然区间右端点要小于\(i\)）的区间，它们的左端点中的最大值必须要小于转移点。这样才能上述性质。
此时我们只需要预处理出包含点i且左端点最小的区间，以及右端点小于\(i\)且左端点最大的区间。我们分别用\(e_{i}\)和\(s_{i}\)表示。
对于读入的每一组\(a,b\)，我们做如下处理：
使用\(a\)来更新\(s_{b+1}\)。这是因为，从\(a\)开始的区间必然不包含\(b+1\)，因此可以这样更新。
使用\(a-1\)来更新\(e_{b}\)。这是因为，从\(a\)开始的区间必然包含\(b\)。
故，更新方法为：
$$ s_{b+1}=Max(s_{b+1},a),e_{b}=Min(e_{b},a-1); $$
然后，对于这样更新得到的结果，我们贪心地处理。
对于\(s\)，我们发现，所有对于点\(i-1\)合法的区间——也就是右端点小于\(i-1\)的区间，一定不包含\(i\)。所以得到：
$$ s_{i}=Max(s_{i},s_{i-1}); $$
对于\(e\)，我们发现，所有对于点\(i+1\)最优的区间——也就是包含\(i+1\)且左端点最小的区间，一定包含\(i\)，否则它对于\(i\)一定不会更优。所以得到：
$$ e_{i}=Min(e_{i+1},e_{i}); $$
由是我们得到了DP需要的两个辅助数组，从而可以开始\(DP\)。
但这个时候我们可以发现，这样子动态确定最大值，如果使用暴力枚举，需要的复杂度是\(O(n)\)的，对于\(2E5\)的数据，通过会很困难。
这时候考虑优化，不过很容易可以发现是单调队列优化。
于是问题得解。

交上去WA10。
这是什么原因呢？
仔细研究一下，发现还是细节的问题。对于-1的特判没有清楚。
修改之后AC。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int n,m,f[200005],s[200005],e[200005];
struct data{
	int v;
	int id;
};
deque<data> q;
inline void psh(int i){
	data x=(data){f[i],i};
	while(!q.empty()&&q.back().v<x.v){
		q.pop_back();
	}
	q.push_back(x);
}
inline int gt(const int &i){
	while(!q.empty()&&q.front().id<s[i]){
		q.pop_front();
	}
	return q.empty()?-1:q.front().v;
}
void init(){
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=n+1;++i){
		e[i]=i-1; 
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a,&b);
		s[b+1]=Max(s[b+1],a),e[b]=Min(e[b],a-1);
	}
	for(int i=2;i<=n+1;++i){
		s[i]=Max(s[i],s[i-1]);
	}
	for(int i=n;i>=1;--i){
		e[i]=Min(e[i+1],e[i]); 
	}
	f[0]=0;
	psh(0);
	int j=1,nw;
	for(int i=1;i<=n+1;++i){
		while(j<=e[i]&&j<=n){
			psh(j);
			++j;
		}
		nw=gt(i);
		f[i]=(nw==-1)?-1:nw+(int)(i<=n);
	}
	printf("%d",f[n+1]);
}
int main(){
	init();
	return 0;
}