「Test」小明的新书

题意：小明即将出版新书，以记录他辉煌的虐题生涯。有 $n$ 家出版社对这本书表示了兴趣，并愿意给小明支付 $p\in[Minn,Maxx]$ 的报酬来得到这本书的出版权，每家出版社的 $Minn$ 和 $Maxx$ 是不一样的。 现在小明希望你帮他找出一个报酬值 $p$，使得他获得的总报酬最多。(每一个 $Minn\leq p\leq Maxx$ 的出版社都会付给小明 $p$ 的报酬，$1\leq n\leq 100000,1\leq Minn,Maxx\leq 10^9$)

题目重点就是找对于每一个报酬值 $p$，有多少家出版社愿意给。

这里我们可以把每一家出版社给的报酬范围转化为区间，很明显，用朴素方法，将区间内的每个数都加 $1$，就能求到问题的答案，而区间修改操作我们可以通过差分与前缀和来完成，所以我们开个结构体，存储位置与差分端点改变的值，利用扫描线的思想，从头到尾不断更新前缀和，且在每次更新的同时求最大值即可(还有一个要点看代码)。

注意一定要开足够的数组范围！！！(否则就会像我一样丢掉 $60$ 分)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,cnt,p;
struct book
{
	long long pos;
	long long val;
}a[401010];//扫描线，数组开4倍!!
long long ans;
bool cmp(book a,book b)
{
	if(a.pos==b.pos)
		return a.val<b.val;
	return a.pos<b.pos;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		a[++cnt]=book{x,1};
		a[++cnt]=book{y,0};//这里添加一个y的位置是为了防止万一没有交集的两个区间，导致取不到最大值
		a[++cnt]=book{y+1,-1};//差分思想
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		p+=a[i].val;//前缀和
		ans=max(ans,a[i].pos*p);//直接扫一遍找最大值
	}
	printf("%lld",ans);
	return 0;
}
//重点在第30行那行代码，容易被忽略，如果两个区间没有交集，需要用这行代码来防止取不到最大值
//反例：
/*
4
1 3
4 6
7 9
10 13
*/
//无第30行代码答案:10
//正确答案:13