library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Fast Set
(DataStructure/fastset.hpp)

• View this file on GitHub
• Last update: 2025-04-06 06:46:04+09:00
• Include: #include "DataStructure/fastset.hpp"

Code

#pragma once

struct FastSet {
    static constexpr int B = 64;
    int n, lg;
    vector<vector<ull>> seg;
    FastSet(int m) : n(m) {
        do {
            seg.push_back(vector<ull>((m + B - 1) / B));
            m = (m + B - 1) / B;
        } while (m > 1);
        lg = seg.size();
    }
    bool operator[](int i) const {
        return (seg[0][i / B] >> (i % B) & 1);
    }
    void insert(int i) {
        rep(h, 0, lg) {
            seg[h][i / B] |= 1ull << (i % B);
            i /= B;
        }
    }
    void erase(int i) {
        rep(h, 0, lg) {
            seg[h][i / B] &= ~(1ull << (i % B));
            if (seg[h][i / B])
                break;
            i /= B;
        }
    }
    // smallest >= i
    int next(int i) {
        rep(h, 0, lg) {
            if (i / B == seg[h].size())
                break;
            ull d = seg[h][i / B] >> (i % B);
            if (!d) {
                i = i / B + 1;
                continue;
            }
            i += lowbit(d);
            for (int g = h - 1; g >= 0; g--) {
                i *= B;
                i += lowbit(seg[g][i / B]);
            }
            return i;
        }
        return -1;
    }
    // largest <= i
    int prev(int i) {
        rep(h, 0, lg) {
            if (i == -1)
                break;
            ull d = seg[h][i / B] << (63 - i % 64);
            if (!d) {
                i = i / B - 1;
                continue;
            }
            i += topbit(d) - (B - 1);
            for (int g = h - 1; g >= 0; g--) {
                i *= B;
                i += topbit(seg[g][i / B]);
            }
            return i;
        }
        return -1;
    }
};

/**
 * @brief Fast Set
 */

#line 2 "DataStructure/fastset.hpp"

struct FastSet {
    static constexpr int B = 64;
    int n, lg;
    vector<vector<ull>> seg;
    FastSet(int m) : n(m) {
        do {
            seg.push_back(vector<ull>((m + B - 1) / B));
            m = (m + B - 1) / B;
        } while (m > 1);
        lg = seg.size();
    }
    bool operator[](int i) const {
        return (seg[0][i / B] >> (i % B) & 1);
    }
    void insert(int i) {
        rep(h, 0, lg) {
            seg[h][i / B] |= 1ull << (i % B);
            i /= B;
        }
    }
    void erase(int i) {
        rep(h, 0, lg) {
            seg[h][i / B] &= ~(1ull << (i % B));
            if (seg[h][i / B])
                break;
            i /= B;
        }
    }
    // smallest >= i
    int next(int i) {
        rep(h, 0, lg) {
            if (i / B == seg[h].size())
                break;
            ull d = seg[h][i / B] >> (i % B);
            if (!d) {
                i = i / B + 1;
                continue;
            }
            i += lowbit(d);
            for (int g = h - 1; g >= 0; g--) {
                i *= B;
                i += lowbit(seg[g][i / B]);
            }
            return i;
        }
        return -1;
    }
    // largest <= i
    int prev(int i) {
        rep(h, 0, lg) {
            if (i == -1)
                break;
            ull d = seg[h][i / B] << (63 - i % 64);
            if (!d) {
                i = i / B - 1;
                continue;
            }
            i += topbit(d) - (B - 1);
            for (int g = h - 1; g >= 0; g--) {
                i *= B;
                i += topbit(seg[g][i / B]);
            }
            return i;
        }
        return -1;
    }
};

/**
 * @brief Fast Set
 */

Back to top page