自动搬运

查看原文

来自洛谷，原作者为

	dottle Cy@?g|^a

搬运于2025-08-24 22:40:04，当前版本为作者最后更新于2022-09-05 19:13:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们先来思考，怎样的 $[x,y]$ 是合法的。

直接给出结论：$[x,y]$ 合法，当且仅当 $[x+1,y]$ 其不包含任意一个左端点，$[x,y-1]$ 不包含任意一个右端点。

比如说 $[x+1,y]$ 包含了端点 $l_i$，那么 $[x,y]$ 一定不被 $[l_i,r_i]$ 包含，但他们有交集，这就不合法了。反之，如果 $[x,y]$ 不被 $[l_i,r_i]$ 包含，但他们有交集，那么要么 $[x+1,y]$ 其包含 $l_i$，要么 $[x,y-1]$ 包含 $r_i$。

接下来考虑代码实现，为了方便，我们把上面对左端点的约束写成 $[x,y-1]$ 不包含任意一个 $l_i-1$，即将读入的左端点向左平移一个位置。这样我们的条件就变成了 $[x,y-1]$ 不包含任意一个端点了。

因为我们想要最大化 $k(y-x)$，那么我们一定是选一段尽可能长的区间作为答案。那么我们选取的 $x$ 一定是某个端点的右边一个位置，选取的 $y$ 一定是 $x$ 后面的第一个端点。可以使用前缀和的方式求出对于两个端点之间，有多少线段覆盖了它。这样，就可以统计答案了。

时间复杂度 $O(x)$，其中 $x$ 是值域大小。

#include<bits/stdc++.h>
#define N 300050
#define int long long
using namespace std;
int f[N],x,y,v[N],mx,pre=1,sum,ans,n;

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&x,&y);
    	v[x-1]=1,v[y]=1;// 标记哪些位置有端点，注意左端点往左移动一个位置
    	f[x]++,f[y+1]--;// x 到 y 位置被覆盖的次数 +1
    	mx=max(mx,y);// 记录最大的坐标
    }
	for(int i=1;i<=mx;i++){
		sum+=f[i];// 计算当前位置被多少个线段覆盖了
		if(v[i])ans=max(ans,sum*(i-pre)),pre=i+1;//若这里有一个端点，则作为 y，与之前记录的 x 更新答案；然后更新 x 为此端点右边一个位置
	}
	printf("%lld",ans);
}