交付树状数组加布隆

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线的最终作品。树状数组（lowbit / fen_build / fen_prefix / fen_range / fen_add）和布隆过滤器的框架都给好了，补全其中的关键函数，然后一次验完五条：前 3 个的和是 56、整段的和是 92；第 2 到第 4 个的和是 52；给第 2 个加 10 之后，前 3 个的和变成 66；布隆过滤器里查 15 是「可能在」、查 10 是「肯定不在」；查 13 是「可能在」——它从没加过，这是一次误判。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步再写个布隆过滤器暴力区间求和为什么超时 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

const vector<long long> A5 = {17, 24, 15, 13, 23};

int lowbit(int x) {
    return x & (-x);
}

vector<long long> fen_build(const vector<long long>& a) {
    int n = (int)a.size();
    vector<long long> t(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += lowbit(j)) t[j] += a[i - 1];
    }
    return t;
}

long long fen_prefix(const vector<long long>& t, int i) {
    // TODO: 往下减 lowbit 累加
    return 0;
}

long long fen_range(const vector<long long>& t, int l, int r) {
    return fen_prefix(t, r) - fen_prefix(t, l - 1);
}

void fen_add(vector<long long>& t, int n, int i, long long v) {
    // TODO: 往上加 lowbit 一路更新
}

int h1(int k) { return k % 8; }
int h2(int k) { return (k * 3) % 8; }

void bloom_add(vector<int>& bits, int k) {
    bits[h1(k)] = 1;
    bits[h2(k)] = 1;
}

string bloom_check(const vector<int>& bits, int k) {
    // TODO: 两位都是 1 才算 可能在
    return "肯定不在";
}

int main() {
    vector<long long> t = fen_build(A5);
    vector<bool> checks;
    checks.push_back(fen_prefix(t, 3) == 56 && fen_prefix(t, 5) == 92);
    checks.push_back(fen_range(t, 2, 4) == 52);
    fen_add(t, 5, 2, 10);
    checks.push_back(fen_prefix(t, 3) == 66);
    vector<int> bits(8, 0);
    for (int k : {17, 24, 15}) bloom_add(bits, k);
    checks.push_back(bloom_check(bits, 15) == "可能在" && bloom_check(bits, 10) == "肯定不在");
    checks.push_back(bloom_check(bits, 13) == "可能在");
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

交付树状数组加布隆

更多题目

全部评论