已完成今日二进制警报器大学习

Redshift_Shine · 2025-07-31 11:12:56 · 算法·理论

前言

二进制警报器是 zky 在 WC2025 前不久提出的一个掀起了巨大波澜的算法，该算法使得一道来自于四年前的经典折半警报器大时限题目鬼街的限时可以被压制到 1s 以下。

对于该算法，zky 本人已经在他的博客中给出了完善的证明，故本人在这篇文章中将给出该算法在鬼街一题中的一种参考实现，在该题的所有样例上的运行总时长略慢于 zky 的代码。此处为我的提交记录。

代码解析

变量声明

int n, m, idx;
using ll = long long;
ll sm[N], tar[N];
vector<int> res, fac[N], zr;
vector<int> id[N][M];
int rt[N], sid[N];
bool vis[N];

对于上述的变量，其意义如下：

::cute-table{tuack}

函数 \operatorname{calc}

ll calc(int x, int shd)
{
    ll tsm = 0;
    for (auto &i : fac[x])
    {
        tsm += sm[i] + (1ll << shd) - (((1ll << shd) - 1) & sm[i]) - 1;
    }
    return tsm;
}

该函数的作用是计算自然数 x 的所有质因子闹鬼次数在不越过 2^{shd} 的倍数的前提下能达到的最大闹鬼次数总和。

特别的，若 shd=0，则该函数用于计算此时自然数 x 的所有质因子的闹鬼次数之和。

函数 \operatorname{proc}

void proc(int x, ll v)
{
    ll msk = (sm[x] ^ (sm[x] + v));
    sm[x] += v;
    vector<int> tmp;
    for (int i = 0; (1ll << i) <= v or ((msk >> i) & 1); i++)
    {
        tmp.swap(id[x][i]);
        for (auto &j : tmp)
        {
            if (vis[j] or sid[j] != i)
                continue;
            if (calc(rt[j], 0) >= tar[j])
            {
                res.emplace_back(j);
                vis[j] = true;
                continue;
            }
            for (; ~sid[j] and calc(rt[j], sid[j]) >= tar[j]; sid[j]--)
                ;
            if (sid[j] == i)
            {
                id[x][i].emplace_back(j);
                continue;
            }
            for (auto &k : fac[rt[j]])
                id[k][sid[j]].emplace_back(j);
        }
        tmp.clear();
    }
}

该函数的作用是在位置 x 进行 v 次闹鬼，并处理对应的达到了重构目标次幂的警报器。

判断区间 (x,x+y] 之间是否包含 2^p 的倍数的方法有两种。

1. 判断 y\ge 2^p。
2. 判断从 x 到 x+y 时 2^p 对应的二进制位是否发生反转。

上述两个条件满足其一即包含 2^p 的倍数。

容易写出 x 到下一个 2^p 的倍数的距离表达式：

通过上式可得出结论：若 (x,x+y] 未越过 2^p 的倍数，则其一定无法越过 2^{p+1} 的倍数。

该函数内声明的变量 msk 用来处理上述的第二个判断条件。

我们从低到高枚举每一个越过的 2^p。注意，这一步一定要从低到高枚举，因为 sid 中的任何元素都不会增加，若从高到低枚举会造成实现上的麻烦。

考虑到可能会存在重构后 sid 不变的位置，使用 tmp 存储在该 sid 上可供重构的警报器编号后将 id_{x,i} 清空。

枚举警报器时，若枚举到已经发出警报的警报器显然可以跳过；同时，若该警报器目前的 sid 与枚举的 sid 不符，可以直接跳过。上一步的理由是，如果在每次 sid 发生改变时清除该警报器所有先前的标记，需要使用 set 等可以动态删除的数据结构，这样会使得时间复杂度无法得到保证并大幅增加运行时间。不如让先前的标记留在那里，待更新时再进行判断。

最后一步处理时，若 sid 不变，则只将该位置的重构标记还原；否则对于该警报器对应的所有因数在新触发点上安装重构标记。这一步保证了重构标记不会对同一个警报器进行两次操作。

主函数

void run()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 2; i <= n; i++)
    {
        if (fac[i].size())
            continue;
        for (int j = i; j <= n; j += i)
            fac[j].emplace_back(i);
    }
    for (ll i = 1, op, x, y, la = 0; i <= m; i++)
    {
        cin >> op >> x >> y;
        y ^= la;
        if (op)
        {
            idx++;
            if (!y)
            {
                zr.emplace_back(idx);
                continue;
            }
            rt[idx] = x;
            for (auto &j : fac[x])
            {
                tar[idx] += sm[j];
            }
            tar[idx] += y;
            sid[idx] = M - 1;
            for (; ~sid[idx] and calc(rt[idx], sid[idx]) >= tar[idx]; sid[idx]--)
                ;
            for (auto &j : fac[x])
            {
                id[j][sid[idx]].emplace_back(idx);
            }
            continue;
        }
        res.clear();
        zr.swap(res);
        for (auto &j : fac[x])
            proc(j, y);
        cout << res.size() << ' ';
        la = res.size();
        sort(res.begin(), res.end());
        for (auto &j : res)
        {
            cout << j << ' ';
        }
        cout << '\n';
    }
}

使用 O(n\log n) 算法处理每个数的质因子。在操作 0 中计算对应数字的目标值并计算触发点。在操作 1 中首先取出阈值为 0 的警报器，随后进行处理。最后要升序排序。

至此，本题完成。

碎碎念

看到二进制警报器的时候还是初三的寒假。那时由于我对这道题不感兴趣，所以就没有做出来。

再后来，各个中考考试科目接踵而来。在中考的压力之下我不得不将编程放下一段时间。最终成绩出来，在数学/英语/物理/化学加起来扣了 23 分的情况下，其他三科任何一科的扣分都接近这个数字甚至更高……好在还是成功地被第三批第一志愿学校录取，结果发现我的分数与分数线相等，而同分序号与末位只隔了将近 60。颇有一种劫后余生的感觉。

这一切都结束之后，我每天都随机找题做，随到了鬼街，想起了二进制警报器。于是，在昨天，我下定决心做出这道题，最后花了 12 个小时解出来了。

不管怎么说，我的 OI 的故事，现在才刚刚开始！