折半/二进制警报器 学习笔记

bamboo12345 · 2026-01-16 20:20:08 · 算法·理论

好像两百年没写学习笔记了？感觉比较新的东西记一个。

并不一定更好的阅读体验。

引入

折半/二进制警报器主要可以解决这样的问题：

有两种操作：

1. 给某个集合加上一个值。如果有满足了某个询问就输出满足了哪些询问

2. 询问一个集合里的数之和在第多少次操作后第一次大于一个值 V_i。

集合大小比较小，大概是常数量级，假设是 k\le 20，n,q\le 2\times 10^5。

我们当然是可以直接整体二分的。但是如果我们的问题要求在线，那就只能用警报器了，感觉以后有一部分的整体二分都可以改成这个东西啊！

做法

折半警报器

首先我们会一个朴素的暴力：每次询问把集合内的数都挂一个询问的记号，每次一个数增加就暴力 check 询问是否合法，显然我构造一个每次加一就变成 q^2 了，很完蛋。

我们考虑一个像乱搞一样的东西，首先我们发现回答一个询问的必要条件是，存在一个数 \ge \frac {V_i} k，那么我们就给集合里的数都塞一个 \frac {V_i} k 的警报器，当某个数增加之后到了这个阈值，我们就令其“报警”，暴力计算这个警报器对应集合是否合法，合法即成立，否则我们记目前集合的和为 s，那么我们再重新把集合里都塞一个 \frac{V_i-s}{k} 的警报器，重复做直到询问被回答。

我们分析一下复杂度，注意到复杂度来源于我们每次“报警”需要重构，所以我们这里是 O(k) 的复杂度，那么会被重构多少次呢？注意到每次“报警”之后 V\to \frac {k-1} k V，所以最多“报警”O(\log_{\frac{k}{k-1}}V) = O(\frac{\ln V}{\ln k - \ln{k-1}}) = O(k\log V)。同时我们需要用一个堆对于每个元素维护最小的警报取出来，所以总复杂度是 O(k^2\log V\log q)。

模板。

二进制警报器

由 zak 发明，挂一个原文的 blog。

我们发现折半警报器有两个很劣的事情，一个是我需要用堆维护报警器，一个是每次报警我需要 O(k) 的复杂度重构一下。我们大概想的是我们有一个较能整体一起进行的方式。比如对于第一个问题，我们就需要我们的警报是一些固定的值，这样就很方便我们用桶排而不用堆进行维护。对于第二个问题，我们需要一种方式能限制一下我们有效报警，也就是需要重构的次数。

我们考虑用二进制报警器，具体的，对于每一个集合我们维护一个阈值 h，当集合中有一个数 a_i\to a_i + w 的时候，如果 (a_i,a_i+w] 跨过了一个 2^h 的倍数，那么我们就报警。如果当前的 h 能在集合内的数都不报警的情况下到达我们需要的值时，我们令 h 减一。

考虑分析一下这样做的复杂度，对于 h=h_0，因为 V_i - \sum a 不能在全都不报警的情况下达到，所以是 O(k2^{h_0}) 的，而对于每个数，报警两次一定会增加 2^{h_0}，所以在 h=h_0 时会报警至多 k 次。报警总次数就是 k\log V 的。

这样还有一个好处是我们只有至多 O(\log V) 个值需要记录，可以不用堆直接桶记录即可，优化掉了 \log q。

但是现在我们还是没有优化掉重构的次数。注意到我们在 h 降到 -1 的时候就等于答案了，我们可以动态记录一个值 lim，代表在 h=h_0 时，我至多在不触发警报的时候满足多少，在每次 h\to h-1 的时候重构这个 lim 即可，这样我们在一次警报的时候就没有必要暴力重构，而是检验这个 lim 是否合法即可。

这样我们就可以把这类问题优化到 O(qk\log V)，同时常数极小，唯一的缺点在于，这个方法的空间复杂度是 O(nk\log V) 的，对比整体二分还是劣了不少。

可以用二进制警报器的方式再写一下模板，放一个我的代码（因为我比较偷懒，所以模板包括下一个例题都写的是 k^2\log V，最后一个是严格的 k\log V）。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5;
int n, m, lab[maxn], lpf[maxn];
int prime[maxn], tot, vis[maxn], lim[maxn], x[maxn];
void prepare() {
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if(!vis[i])
            prime[++tot] = i, lpf[i] = i;
        for (int j = 1; j <= tot && prime[j] * i <= n; j++) {
            vis[i * prime[j]] = 1;
            lpf[i * prime[j]] = prime[j];
            if(i % prime[j] == 0)
                break;
        }
    }
}
int idx;
vector<int> pos[maxn];
vector<int> get_pos(int x) {
    vector<int> t;
    int lst = 0;
    while(x != 1) {
        if(lst != lpf[x])
            t.push_back(lpf[x]), lst = lpf[x], x /= lst;
        else
            x /= lst;
    } 
    return t;
}
vector<int> t;
bool cross(int l, int r, int v) {
    return r / v - l / v;
}
struct node {
    int p, val;
    friend bool operator<(node x, node y) {
        return x.val > y.val;
    }
} ;
int use[maxn];
vector<int> q[64][maxn];
int a[maxn];
queue<int> tp;
int get_nxt(int x, int y) {
    return (x / y + 1) * y;
}
vector<int> ans;
void renew(int p, int v) {
    vector<int> res;
    if(v == 0)
        return ;
    for (int i = 0; i < 64; i++) {
        if(cross(a[p], a[p] + v, (1ll << i))) {
            for (int j = 0; j < q[i][p].size(); j++) {
                int post = q[i][p][j];
            //  cout << lab[post] << " " << post << " " << i << endl;
                if(lab[post] != i || use[post])
                    continue;
                int rest = v;
                for (int i = 0; i < pos[post].size(); i++) {
                    int nwp = pos[post][i];
                    rest += a[nwp];
                }
                if(rest >= lim[post]) {
                    ans.push_back(post);
                    use[post] = 1;
                }
                else 
                    tp.push(post);
            }
            q[i][p].clear();
        }
    }
    a[p] += v;
    while(!tp.empty()) {
        int t = tp.front(); tp.pop();
        int bg = lab[t];
        while(1) {
            int r = 0;
            for (int i = 0; i < pos[t].size(); i++)
                r += get_nxt(a[pos[t][i]], (1ll << lab[t])) - 1;
            if(r >= lim[t]) 
                lab[t]--;
            else
                break;
        }
        if(bg != lab[t]) {
            for (int i = 0; i < pos[t].size(); i++)
                q[lab[t]][pos[t][i]].push_back(t);
        }
        else 
            q[lab[t]][p].push_back(t);
    }
}
signed main() {
    cin >> n >> m;
    prepare();
    int lst = 0;
    vector<int> rm;
//  cout << get_nxt(0, (1ll << 61)) << endl;
    while(m--) {
        int op, x, y; cin >> op >> x >> y;
        y ^= lst;
        if(op == 0) {
            t = get_pos(x);
            ans.clear();
            for (int i = 0; i < t.size(); i++) 
                renew(t[i], y);
            for (int i = 0; i < rm.size(); i++)
                ans.push_back(rm[i]);
            rm.clear();
        //  cout << "adfafasdgag";
            sort(ans.begin(), ans.end());
            cout << ans.size() << " ";
            for (int i = 0; i < ans.size(); i++)
                cout << ans[i] << " ";
            cout << endl;
        //  cout << lab[1] << endl;
            lst = ans.size();
            ans.clear();
        }
        else {
            t = get_pos(x);
            idx++;
            pos[idx] = t;
            lab[idx] = 51;
            if(!y) {
                rm.push_back(idx);
                continue;
            }
            lim[idx] = y;
            for (int i = 0; i < pos[idx].size(); i++)
                lim[idx] += a[pos[idx][i]];
            int r = 0;
            while(1) {
                int r = 0;
                for (int i = 0; i < pos[idx].size(); i++)
                    r += get_nxt(a[pos[idx][i]], (1ll << lab[idx])) - 1;
                if(r >= lim[idx]) 
                    lab[idx]--;
                else
                    break;
            }
            for (int i = 0; i < pos[idx].size(); i++)
                q[lab[idx]][pos[idx][i]].push_back(idx);
        }
    }
    return 0;
}

例题

qoj7415 Fast Spanning Tree

deepseek 因为我复制的时候小于等于号被吃掉了导致看不懂题，被硬控了 20min。

题意：给出若干条带权边，每个点有点权，我们一开始有一个完全空的图，重复做以下操作。

• 如果不存在边 (a,b,v) 满足 a,b 不连通且 a 所在连通块点权和加上 b 所在连通块点权之和 \ge v，则结束操作。

• 否则找到满足条件的标号最小的边 (a,b,v)，将 (a,b,v) 加入图中。