题解 P2352 【队爷的新书】

· · 题解

为什么题解区那么多人喜欢把差分弄成扫描线啊/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最优解