Fu_L's Library

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

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: BitVector
(src/data_structure/bit_vector.hpp)

BitVector

WaveletMatrix などのための補助データ構造です.
基本的には内部的にしか使用しないと思うので,把握する必要はありません.

Depends on

Required by

Verified with

Code

#pragma once
#include "../template/template.hpp"
#if __has_include(<immintrin.h>)
#include <immintrin.h>
#define CP_LIBRARY_TARGET_POPCNT __attribute__((target("popcnt")))
#define CP_LIBRARY_TARGET_BMI __attribute__((target("bmi")))
#define CP_LIBRARY_TARGET_BMI2_POPCNT __attribute__((target("bmi2,popcnt")))
#else
#define CP_LIBRARY_TARGET_POPCNT
#define CP_LIBRARY_TARGET_BMI
#define CP_LIBRARY_TARGET_BMI2_POPCNT
#endif
CP_LIBRARY_TARGET_POPCNT inline uint32_t popcount64(const uint64_t x) {
#if __has_include(<immintrin.h>)
    return _mm_popcnt_u64(x);
#else
    return __builtin_popcountll(x);
#endif
}
CP_LIBRARY_TARGET_BMI2_POPCNT inline uint64_t low_bits(const uint64_t x, const uint32_t n) {
#if __has_include(<immintrin.h>)
    return _bzhi_u64(x, n);
#else
    return n == 64 ? x : x & ((uint64_t(1) << n) - 1);
#endif
}
CP_LIBRARY_TARGET_BMI inline uint32_t lowbit(const uint32_t x) {
#if __has_include(<immintrin.h>)
    return _blsi_u32(x);
#else
    return x & -x;
#endif
}
CP_LIBRARY_TARGET_BMI inline uint32_t clear_lowbit(const uint32_t x) {
#if __has_include(<immintrin.h>)
    return _blsr_u32(x);
#else
    return x & (x - 1);
#endif
}
struct BitVector {
    using u32 = uint32_t;
    using i64 = int64_t;
    using u64 = uint64_t;
    static constexpr u32 w = 64;
    vector<u64> block;
    vector<u32> count;
    u32 n, zeros;
    inline u32 get(const u32 i) const {
        return u32(block[i / w] >> (i % w)) & 1u;
    }
    inline void set(const u32 i) {
        block[i / w] |= 1ULL << (i % w);
    }
    BitVector() {}
    BitVector(const int _n) {
        init(_n);
    }
    __attribute__((optimize("O3,unroll-loops"))) void init(const int _n) {
        n = zeros = _n;
        block.assign(n / w + 1, 0);
        count.assign(block.size(), 0);
    }
    CP_LIBRARY_TARGET_POPCNT void build() {
        for(u32 i = 1; i < block.size(); ++i) {
            count[i] = count[i - 1] + popcount64(block[i - 1]);
        }
        zeros = rank0(n);
    }
    inline u32 rank0(const u32 i) const {
        return i - rank1(i);
    }
    CP_LIBRARY_TARGET_BMI2_POPCNT inline u32 rank1(const u32 i) const {
        return count[i / w] + popcount64(low_bits(block[i / w], i % w));
    }
};
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/bit_vector.hpp"
#if __has_include(<immintrin.h>)
#include <immintrin.h>
#define CP_LIBRARY_TARGET_POPCNT __attribute__((target("popcnt")))
#define CP_LIBRARY_TARGET_BMI __attribute__((target("bmi")))
#define CP_LIBRARY_TARGET_BMI2_POPCNT __attribute__((target("bmi2,popcnt")))
#else
#define CP_LIBRARY_TARGET_POPCNT
#define CP_LIBRARY_TARGET_BMI
#define CP_LIBRARY_TARGET_BMI2_POPCNT
#endif
CP_LIBRARY_TARGET_POPCNT inline uint32_t popcount64(const uint64_t x) {
#if __has_include(<immintrin.h>)
    return _mm_popcnt_u64(x);
#else
    return __builtin_popcountll(x);
#endif
}
CP_LIBRARY_TARGET_BMI2_POPCNT inline uint64_t low_bits(const uint64_t x, const uint32_t n) {
#if __has_include(<immintrin.h>)
    return _bzhi_u64(x, n);
#else
    return n == 64 ? x : x & ((uint64_t(1) << n) - 1);
#endif
}
CP_LIBRARY_TARGET_BMI inline uint32_t lowbit(const uint32_t x) {
#if __has_include(<immintrin.h>)
    return _blsi_u32(x);
#else
    return x & -x;
#endif
}
CP_LIBRARY_TARGET_BMI inline uint32_t clear_lowbit(const uint32_t x) {
#if __has_include(<immintrin.h>)
    return _blsr_u32(x);
#else
    return x & (x - 1);
#endif
}
struct BitVector {
    using u32 = uint32_t;
    using i64 = int64_t;
    using u64 = uint64_t;
    static constexpr u32 w = 64;
    vector<u64> block;
    vector<u32> count;
    u32 n, zeros;
    inline u32 get(const u32 i) const {
        return u32(block[i / w] >> (i % w)) & 1u;
    }
    inline void set(const u32 i) {
        block[i / w] |= 1ULL << (i % w);
    }
    BitVector() {}
    BitVector(const int _n) {
        init(_n);
    }
    __attribute__((optimize("O3,unroll-loops"))) void init(const int _n) {
        n = zeros = _n;
        block.assign(n / w + 1, 0);
        count.assign(block.size(), 0);
    }
    CP_LIBRARY_TARGET_POPCNT void build() {
        for(u32 i = 1; i < block.size(); ++i) {
            count[i] = count[i - 1] + popcount64(block[i - 1]);
        }
        zeros = rank0(n);
    }
    inline u32 rank0(const u32 i) const {
        return i - rank1(i);
    }
    CP_LIBRARY_TARGET_BMI2_POPCNT inline u32 rank1(const u32 i) const {
        return count[i / w] + popcount64(low_bits(block[i / w], i % w));
    }
};
Back to top page