..

P8551 Bassline

2022/10/16 AC 300 祭 Bassline

本文思路来自 dottle
在其基础上扩写而成
让我们感谢他的贡献

题目链接：P8851 Bassline - 洛谷

读题

先对题目中的易混淆点进行强调：

你需要选择两个整数 $x\le y$，满足：

  • 对于所有区间 $[l_i,r_i]$（$1\le i \le n$），以下两个条件之一满足：
    1. $[x,y]$ 被 $[l_i,r_i]$ 包含，换言之， $[x,y]\cap[l_i,r_i]=[x,y]$。
    2. $[x,y]$ 与 $[l_i,r_i]$ 无交集，换言之，$[x,y]\cap[l_i,r_i]=\varnothing$。

若有 $k$ 个区间满足条件 1，则你的得分是 $k(y-x)$。输出你最大的可能的得分。

这里 $x, y$ 是我们要求的数，$k$ 也是。（废话……

但关于 $k$ 的来源，请注意，是满足包含 $[x, y]$，或与 $[x, y]$ 无交集的 $[l_i, r_i]$，而 $[l_i, r_i]$ 是题目给定的数据。

换言之，$k$ 的含义，并不是有多少个 $[x, y]$ 满足上述条件（那样 $k$ 将为定值），而是针对我们给出的 $[x, y]$，有多少个输入给定的 $[l_i, r_i]$ 将其包含或与之无交集。

这样一来，$k$ 的值是随不同的 $[x, y]$ 而变化的。我们只需根据每一个合法的 $[x, y]$，求出有多少个 $[l_i, r_i]$ 满足条件，取最大值即是答案。

解题

要 $[x, y]$ 合法，那么 $(x, y]$ 内不能出现任何一个 $l_i$，同时 $[x, y]$ 内不能出现任何一个 $r_i$。

这里的 $(), []$ 都没有打错。

  • $()$ 表示开区间，不包含左右端点；
  • $[]$ 表示闭区间，包含左右端点；

当 $k$ 的值一定时（满足条件的 $[l_i, r_i]$ 一定），$y - x$ 最大时答案最大。

我们考虑两种条件：
由于 $l, r$ 在这里作为左右端点的约束条件存在，其下标不一定相同，故舍去。

  1. $[x, y]$ 被 $[l, r]$ 包含：
    $x = l, y = r$；
  2. $[x, y]$ 与 $[l, r]$ 无交集：
    $x = r + 1, y = l - 1$. 我们发现边界出现 $+1, -1$ 不是很好处理，于是考虑：
    令 $l’ = l - 1$，
    则：
  3. $[x, y]$ 被 $[l, r]$ 包含：
    $x = l’ + 1, y = r$；
  4. $[x, y]$ 与 $[l, r]$ 无交集：
    $x = r + 1, y = l’$.

这样一来，两种条件的区间形式就统一了。

不难发现：

  • 每个 $l’ + 1, r + 1$ 可以作为 $x$;
  • 每个 $l’, r$ 可以作为 $y$.
    即
  • 每个 $l, r + 1$ 可以作为 $x$；
  • 每个 $l - 1, r$ 可以作为 $y$.

可以推出，我们考虑的每一个 $y$，都可以将 $y + 1$ 作为下一次考虑的 $x$。

写题

用 $point_i$ 表示第 $i$ 位能否作为 $y$，在读入 $l_i, r_i$ 时，将 $l_i - 1, r_i$ 作好标记；
用 $cover_i$ 以差分的方式表示第 $i$ 位被多少 $[l_i, r_i]$ 覆盖，在读入 $l_i, r_i$ 时，将 $cover_l + 1, cover_{r + 1} - 1$；
用 $last$ 存储 $y$ 最后一次出现的位置，即 $\max(r_i)$，以便与后续遍历。

遍历下标 $i$，同时用 $cnt$ 计算 $cover_i$ 的前缀和，即可得到第 $i$ 位的 $k$；
若 $i$ 可以作为 $y$：

  • 计算 $k (y - x)$ 的值，并记录；
  • 更新 $l = i + 1$（$l$ 初始值为 $1$.

代码

#include <cstdio>
#include <algorithm>

const int maxn = 3e5 + 10;

int n;
int x, y;

int point[maxn];
int cover[maxn];
int last;
int cnt;
int pre = 1;
long long ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
	scanf("%d%d", &x, &y);
    	point[x - 1] = 1;
        point[y] = 1;
    	cover[x]++;
        cover[y + 1]--;
    	last = std::max(last, y);
    }

    for (int i = 1; i <= last; i++) {
	cnt += cover[i];
	if (point[i]) {
            ans = std::max(ans, (long long)cnt * (i - pre));
            pre = i + 1;
        }
    }

    printf("%lld\n", ans);

    return 0;
}

备注

此题中 $1 \le n \le 3 \times {10}^5$，数组需开全局，否则会 WA。

Lyccrius 交了 17 遍才过。