This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "data_structure/bitVector.hpp"
#pragma once #include "../template/int_alias.hpp" /* reference: https://misteer.hatenablog.com/entry/bit-vector */ #include <vector> namespace ebi { struct bitVector { u32 length, cn, bn; static u32 cw, bw; // chunk, block の長さ cw = (lg N)^2, bw = (lg N)/2 とする. std::vector<u16> bit; std::vector<u32> chunk; std::vector<std::vector<u16>> blocks; bitVector(int n) : length(n) { cn = (length + cw - 1) / cw; bn = cw / bw; bit.assign(cn * bn, 0); chunk.assign(cn + 1, 0); blocks.assign(cn, std::vector<u16>(bn, 0)); } void set(int k, int b) { u32 i = k / bw; u32 j = k % bw; if (b == 0) { bit[i] &= ~(1 << j); } else if (b == 1) { bit[i] |= (1 << j); } } int access(int k) { u32 i = k / bw; u32 j = k % bw; return bit[i] >> j & 1; } void build() { chunk[0] = 0; for (u32 i = 0; i < cn; i++) { blocks[i][0] = 0; for (u32 j = 0; j < bn - 1; j++) { blocks[i][j + 1] = blocks[i][j] + __builtin_popcount(bit[i * bn + j]); } chunk[i + 1] = chunk[i] + blocks[i][bn - 1] + __builtin_popcount(bit[(i + 1) * bn - 1]); } } // [0, r)に存在する1の数をO(1)で計算する. int rank(int r) { u32 i = r / cw; u32 j = (r % cw) / bw; u32 k = r % bw; u32 leftover = bit[i * bn + j] & ((1 << k) - 1); if (i == cn) return chunk[i]; return chunk[i] + blocks[i][j] + __builtin_popcount(leftover); } int select(int k) { if (k == 0) return 0; if (rank(length) < k) return -1; u32 l = 0; u32 r = length; while (r - l > 1) { u32 mid = (r + l) / 2; if (rank(mid) >= k) { r = mid; } else { l = mid; } } return r; } int select0(int k) { if (k == 0) return 0; if (length - rank(length) < (u32)k) return -1; u32 l = 0; u32 r = length; while (r - l > 1) { u32 mid = (r + l) / 2; if (mid - rank(mid) >= (u32)k) { r = mid; } else { l = mid; } } return r; } }; u32 bitVector::cw = 1024; u32 bitVector::bw = 16; } // namespace ebi
#line 2 "data_structure/bitVector.hpp" #line 2 "template/int_alias.hpp" #include <cstdint> namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 4 "data_structure/bitVector.hpp" /* reference: https://misteer.hatenablog.com/entry/bit-vector */ #include <vector> namespace ebi { struct bitVector { u32 length, cn, bn; static u32 cw, bw; // chunk, block の長さ cw = (lg N)^2, bw = (lg N)/2 とする. std::vector<u16> bit; std::vector<u32> chunk; std::vector<std::vector<u16>> blocks; bitVector(int n) : length(n) { cn = (length + cw - 1) / cw; bn = cw / bw; bit.assign(cn * bn, 0); chunk.assign(cn + 1, 0); blocks.assign(cn, std::vector<u16>(bn, 0)); } void set(int k, int b) { u32 i = k / bw; u32 j = k % bw; if (b == 0) { bit[i] &= ~(1 << j); } else if (b == 1) { bit[i] |= (1 << j); } } int access(int k) { u32 i = k / bw; u32 j = k % bw; return bit[i] >> j & 1; } void build() { chunk[0] = 0; for (u32 i = 0; i < cn; i++) { blocks[i][0] = 0; for (u32 j = 0; j < bn - 1; j++) { blocks[i][j + 1] = blocks[i][j] + __builtin_popcount(bit[i * bn + j]); } chunk[i + 1] = chunk[i] + blocks[i][bn - 1] + __builtin_popcount(bit[(i + 1) * bn - 1]); } } // [0, r)に存在する1の数をO(1)で計算する. int rank(int r) { u32 i = r / cw; u32 j = (r % cw) / bw; u32 k = r % bw; u32 leftover = bit[i * bn + j] & ((1 << k) - 1); if (i == cn) return chunk[i]; return chunk[i] + blocks[i][j] + __builtin_popcount(leftover); } int select(int k) { if (k == 0) return 0; if (rank(length) < k) return -1; u32 l = 0; u32 r = length; while (r - l > 1) { u32 mid = (r + l) / 2; if (rank(mid) >= k) { r = mid; } else { l = mid; } } return r; } int select0(int k) { if (k == 0) return 0; if (length - rank(length) < (u32)k) return -1; u32 l = 0; u32 r = length; while (r - l > 1) { u32 mid = (r + l) / 2; if (mid - rank(mid) >= (u32)k) { r = mid; } else { l = mid; } } return r; } }; u32 bitVector::cw = 1024; u32 bitVector::bw = 16; } // namespace ebi