黑洞 暴力二分 峰值37ms可过

· · 个人记录

刚开始的思路是搓一个O(LogN+M*LogN)的暴力二分

显然由于极限情况下M=1e9，因此T，只得72pts

用vector去重后，每次跳到二分的变化界限，重复的数以乘代加

优化为O(LogN+N*LogN)，轻松过oj；洛谷峰值82ms

代码：

//纯暴力+vec优化，跑得飞快
//时间复杂度：O(N*LogN+LogN)

#include<bits/stdc++.h>
#define N 200005
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define mod (int)(1e9+7)
using namespace std;
class Quick_IO
{
  public:
    template<typename T>
    void read(T &r)
    {
        T x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        r = x * f;
    }
    template<typename T, typename... Args>
    void read(T &tmp, Args &... tmps)
    {
        read(tmp);
        read(tmps...);
    }
} io;
#define Freopen \
    freopen("hole.in", "r", stdin); \
    freopen("hole.out", "w", stdout);

int n, High = inf, ans, Last;
int Low[N], m[N];
vector<int> Low2;
#define siz2 (Low2.size())

int Pow(int a, int n, int p)   //快速幂求 a^n % p
{
    int ans = 1;
    while (n)
    {
        if (n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

signed main()
{
    //Freopen;
    io.read(n);
    for (int i = 1; i <= n; i++) io.read(m[i]);
    for (int i = 1, a; i <= n; i++)
    {
        io.read(a);
        Low[i] = min(a - 1, m[i] - a);
        High = min(High, max(a - 1, m[i] - a)); //最大边界
    }

    sort(Low + 1, Low + 1 + n);     //排序
    for (int i = 1; i <= n; i++)    //去重
    {
        if (Low[i] >= High) break;  //大的不要
        if (siz2 == 0) Low2.emplace_back(Low[i]);
        else if (Low2[siz2 - 1] < Low[i]) Low2.emplace_back(Low[i]);
    }
    Low2.emplace_back(High);

    for (int i = 0, k, z, t; i < siz2; i++)
    {
        k = Low2[i], t = k - Last;  //t代表需要加几次，乘法代替以前枚k++
        z = Low + 1 + n - lower_bound(Low + 1, Low + 1 + n, k); //获取当前大于等于k的有几个
        ans += (Pow(2, z, mod) * (t % mod)) % mod;
        ans %= mod, Last = k;
    }
    cout << (ans + 1) % mod;    //黑洞自身
}