Bassline

dottle · 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);
}