主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
已完成今日二进制警报器大学习
最后更新于 2025-07-31 11:18:33
作者
Redshift_Shine
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
## 前言 [二进制警报器](https://www.cnblogs.com/zkyJuruo/p/18668862)是 zky 在 WC2025 前不久提出的一个掀起了巨大波澜的算法,该算法使得一道来自于四年前的经典折半警报器大时限题目[鬼街](https://www.luogu.com.cn/problem/P7603)的限时可以被压制到 1s 以下。 对于该算法,zky 本人已经在他的博客中给出了完善的证明,故本人在这篇文章中将给出该算法在[鬼街](https://www.luogu.com.cn/problem/P7603)一题中的一种参考实现,在该题的所有样例上的运行总时长**略慢于** zky 的代码。[此处](https://www.luogu.com.cn/record/227897106)为我的提交记录。 ## 代码解析 ### 变量声明 ```c++ 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} | 变量名称 | 意义 | | :-: | :-: | | $n,m$ | 如题目所示 | | $idx$ | 目前警报器的最大编号 | | $sm_i$ | 目前位置 $i$ 的总闹鬼次数 | | $tar_i$ | 警报器 $i$ 的报警阈值 | | $res$ | 本次查询报警的警报器编号 | | $fac_i$ | 自然数 $i$ 的所有质因子 | | $id_{x,h}$ | 所有监控范围包含 $x$ 且重构目标次幂为 $h$ 的警报器编号 | | $rt_i$ | 警报器 $i$ 监控的整数 | | $sid_i$ | 警报器 $i$ 目前的重构目标次幂 | | $vis_i$ | 警报器 $i$ 是否已经报警 | ### 函数 $\operatorname{calc}$ ```c++ 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}$ ```c++ 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$ 的倍数的距离表达式: $$ 2^p-((2^p-1)\&x) $$ 通过上式可得出结论:若 $(x,x+y]$ 未越过 $2^p$ 的倍数,则其一定无法越过 $2^{p+1}$ 的倍数。 该函数内声明的变量 $msk$ 用来处理上述的第二个判断条件。 我们从低到高枚举每一个越过的 $2^p$。**注意,这一步一定要从低到高枚举**,因为 $sid$ 中的任何元素都不会增加,若从高到低枚举会造成实现上的麻烦。 考虑到可能会存在重构后 $sid$ 不变的位置,使用 $tmp$ 存储在该 $sid$ 上可供重构的警报器编号后将 $id_{x,i}$ 清空。 枚举警报器时,若枚举到已经发出警报的警报器显然可以跳过;同时,若该警报器目前的 $sid$ 与枚举的 $sid$ 不符,可以直接跳过。上一步的理由是,如果在每次 $sid$ 发生改变时清除该警报器所有先前的标记,需要使用 set 等可以动态删除的数据结构,这样会使得时间复杂度无法得到保证并大幅增加运行时间。不如让先前的标记留在那里,待更新时再进行判断。 最后一步处理时,若 $sid$ 不变,则**只将该位置的重构标记还原**;否则对于该警报器对应的所有因数在新触发点上安装重构标记。这一步保证了重构标记不会对同一个警报器进行两次操作。 ### 主函数 ```c++ 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 的故事,现在才刚刚开始!
正在渲染内容...
点赞
0
收藏
0