自动搬运

查看原文

来自洛谷，原作者为

	w23c3c3 这个人不懒，但还是什么也没留下

搬运于2025-08-24 21:36:41，当前版本为作者最后更新于2021-01-28 09:16:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

为什么题解区那么多人喜欢把差分弄成扫描线啊/yun

这题是求一个点$x$，最大化$x\sum\limits_{i=1}^n[x\in[l_i,r_i]]$

和别的题解想法一样，显然在右端点时最优

这时候就只需要求每个右端点被多少个区间包含

这时候每个右端点互不相关，为简化讨论先从小到大考虑右端点

先看左端点的限制，那么也就是求多少个$l_i\leq x(r_k)$

这个显然sort一遍$l_i$，然后依次向后加入就行

再看$r_i$的限制，显然比他小的右端点（也就是之前枚举的右端点）都不行，他以及他之后的右端点都可以

这时候记录一下在他前面枚举了多少右端点就行了

这时候我们发现左端点和右端点的限制完全无关，这时候可以把左右端点分开，分别sort一遍，这时候在他前面枚举的右端点就是这个点的下标$-1$

然后基本上就能解决了

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
long long ans,g,n,i,l,a[100001],b[100001];
int main(){
	scanf("%lld",&n);
	for(i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
	sort(a+1,a+n+1);sort(b+1,b+n+1);
	l=1;
	for(i=1;i<=n;i++){
		while(l<=n&&a[l]<=b[i])l++;    //这里l是左端点<=r[i]的最大值的后一个，所以其实应该是l-1个
		ans=max((l-i)*b[i],ans);      //所以这里就变成(l-1-(i-1))*r[i]=(l-i)*r[i]
	}
	printf("%lld\n",ans);
}

喜提$O_2$最优解