自动搬运

查看原文

来自洛谷，原作者为

	x义x “我们要走多远？”“一百万年。”

搬运于2025-08-24 21:45:09，当前版本为作者最后更新于2019-07-29 14:39:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

UPD9/27：修正了第二张图片。对大家造成的不便请谅解。

显然这是一个DP题……（当然它也不太显然地是一个差分约束但是被卡了）（其实差分约束还是能过的）

首先定义状态：$f[i]$表示$i$位置必须有一头斑点奶牛，（包括$i$位置的那头牛）前面最多能放多少斑点奶牛。

显然

$$f[i]=\max(f[j])+1\quad(j<i,j\text{满足限制})$$

也就是$[j+1,i-1]$里不放奶牛，只在$f[i]$多放一头奶牛。

问题主要在于所谓的满足限制。题意中说一个区间里必须有1头牛，我们把它转化成一个区间里最多有1头牛，最少有1头牛，这是一个常用的技巧。下面分别进行分析。

限制1：区间$[l,r]$最多有1头奶牛

考虑$j<i$的两个都在$[l,r]$中的位置$j,i$。显然$i$不能通过$j$转移得到，不然$[l,r]$中就会有两头奶牛了。

也就是说：

对于任意包含$i$的区间$[l,r]$，合法的$j$必须小于$l$。

我们其实不用考虑所有的包含$i$的区间，我们只需要这些区间里$l$最小的那一个即可。它的“影响力”最大。

$$\color{grey}\tiny\texttt{红框们使得图中指出的所有的j都不合法。}$$

我们定义：$minl[i]$为包含$i$的区间中最小的$l$。我们可以很快地从$N$到$1$扫一遍得到它：

$$minl[i]=\min(\text{右端点恰好是}i\text{的区间的最小的}l,minl[i+1]) $$

可以理解为：包含$i$的区间要么右端点就是$i$，要么右端点比$i$大。

“$\text{右端点恰好是}i\text{的区间的最小的}l$”很好得出，弄个桶即可。

限制2：区间$[l,r]$至少有1头奶牛

考虑$j<l,r<i$的区间$[l,r]$和位置$j,i$。显然$i$不能通过$j$转移得到，不然$[l,r]$中一头奶牛也没有。

也就是说：

对于任何$r<i$（整个区间都在$i$之前）的区间，合法的$j$必须大于等于$l$。

同样，我们其实不用考虑所有的$r<i$的区间，我们只需要这些区间里$l$最大的那一个即可。小于它的$j$都不合法。

$$\color{grey}\tiny\texttt{蓝框们使得图中指出的两个j都不合法，但是那个用红色标记的j是合法的。} $$

（复读ing）

同样我们还是只考虑右端点小于$i$的最大的$l$。称它为$maxl[i]$。我们同样可以从$1$到$N$扫一遍得出它：

$$maxl[i]=\max(\text{右端点恰好是}i-1\text{的区间的最大的}l,maxl[i-1]) $$

那么，我们终于得到一个舒服一点的转移方程：

$$f[i]=\max(f[j])+1\quad (maxl[i]\le j<minl[i])$$

注意到$maxl[i],minl[i]$都单调不降，所以我们可以使用单调队列优化。参见P1886。

代码如下：

（不建议抄，因为此题细节多的一匹）

#include <bits/stdc++.h>
using namespace std;

int N,M;
int minl[200005],maxl[200005];

int q[200005],h,t;
int f[200005];

int main(){
	//注意我们设了一个虚拟节点N+1判无解 
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N+1;i++) minl[i]=i;
	for(int i=1;i<=M;i++){
		int l,r;scanf("%d%d",&l,&r);
		//这里偷懒了，对应的桶和minl,maxl合并了 
		minl[r]=min(minl[r],l);
		maxl[r+1]=max(maxl[r+1],l);
	}
	//扫 
	for(int i=N;i>=1;i--)
		minl[i]=min(minl[i],minl[i+1]);
	for(int i=1;i<=N+1;i++)
		maxl[i]=max(maxl[i],maxl[i-1]);
	
	//单调队列和转移部分 
	h=1;q[++t]=0;int j=1;
	for(int i=1;i<=N+1;i++){
		for(;j<minl[i];j++)if(f[j]!=-1){	//新的合法j 
			while(h<=t&&f[q[t]]<f[j]) t--;
			q[++t]=j;
		}
		while(h<=t&&q[h]<maxl[i]) h++;
		if(h<=t) f[i]=f[q[h]]+(i!=N+1);		//选假的N+1不能有贡献 
		else f[i]=-1;
	} 
	printf("%d\n",f[N+1]);
	
	return 0;
}