题解：P11214 【MX-J8-T2】黑洞

· · 题解

非常难的一道题，想了 150 分钟。（ 怎么降黄了

根据题意，对每一维同时增加或减少一个正整数 C，能得到被黑洞吞噬的点 A。

把每一维对应成一根竹竿，表示 能够增减的范围，以 样例 #3 为例：

方便起见，调换这些竹竿的方向，把距离 0 较长的一端放在上面，按另一端的长度排序。

因为有竹竿 [3, -1] ，所以 C \leq 3，那么对于所有竹竿，绝对值大于 3 的部分是没用的。

也就是说，对于所有输入，可以转化成 n 个竹竿，其中第 i 个竹竿 上端长度为 L，下端长度为 x_i，保证 x_{i-1} \le x_i 且 x_i \le L 。

考虑第 i 个竹竿对 A 取值数量的贡献 p_i ，可以写成：

p_i = 2^{n - i + 1}(x_i-x_{i-1})

答案是 1 + \Sigma {p} + (L-x_n) ，其中 1 是输入的点本身，L-x_n 是 C > x_n 的情况 。

时间复杂度 O(n \log n) ，瓶颈在排序，代码不难写：

#include <bits/stdc++.h>
#define u64 unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
#define i64 long long

const i64 MAXN = 2e5 + 64;

const i64 MOD = 1000000007;
#define mod(x) ((x) % MOD)

i64 m[MAXN], a[MAXN], n;

i64 x[MAXN], L = inf, sigp;

void solve()
{
    assert(scanf("%lld", &n));
    for (i64 i = 1; i <= n; ++i) assert(scanf("%lld", &m[i]));
    for (i64 i = 1; i <= n; ++i) assert(scanf("%lld", &a[i]));
    for (i64 i = 1, l; i <= n; ++i)
    {
        l = m[i] - a[i], x[i] = a[i] - 1;
        if (l < x[i]) std::swap(l, x[i]);
        L = std::min(L, l);
    }
    for (i64 i = 1; i <= n; ++i) x[i] = std::min(L, x[i]);
    std::sort(x + 1, x + 1 + n, std::less<i64>());
    for (i64 i = n, k = 2; i; --i, k = mod(k << 1))
    {
        sigp = mod(sigp + (x[i] - x[i - 1]) * k);
    }
    printf("%lld\n", mod(1 + sigp + (L - x[n])));
}

signed main()
{
    solve();
    return 0;
}