This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#include <cinttypes> #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #include "../strc_023_compact_bitvector.cpp" int main() { int N; cin >> N; vector<int> vec(N); for(int i=0; i<N; i++) cin >> vec[i]; SuccinctBitVector<> sb(vec); for(int i=0; i<N; i++) { cout << sb.rank(i) << " "; } cout << endl; for(int i=0; i<N; i++) { int a = sb.select_nxt(i); cout << (a < 0 ? -1 : a + 1) << " "; } cout << endl; for(int i=0; i<N; i++) { int a = sb.select_pre(i); cout << (a < 0 ? -1 : a + 1) << " "; } cout << endl; cout << "count: " << sb.count() << ", size = " << sb.size() << endl; /* while(true) { int q; cin >> q; if(q == 1) { int k; cin >> k; k--; cout << sb.rank(k) << endl; } if(q == 2) { int k; cin >> k; k--; int a = sb.select_nxt(k); cout << (a < 0 ? -1 : a + 1) << endl; } if(q == 3) { int k; cin >> k; k--; int a = sb.select_pre(k); cout << (a < 0 ? -1 : a + 1) << endl; } if(q == 4) { int l, r; cin >> l >> r; l--; cout << sb.rank(l, r) << endl; } } */ return 0; }
#line 1 "structure/verify/verify_strc_023_compact_bitvector.cpp" #include <cinttypes> #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #line 2 "structure/strc_023_compact_bitvector.cpp" // @title 簡潔ビットベクトル (compact bit vector) // 簡潔ビットベクトル (数列の長さを N とする) // n_big <- log^2(N) (N = 2^32 としたとき、n_big = 32^2 = 1024 = 2^10) // n_sml <- log(N) / 2 (N = 2^32 としたとき、n_sml = 32/2 = 16 = 2^4) // n_blk <- n_big を n_sml で割ったもの // ln_big, ln_sml には、それぞれ log(n_big), log(n_sml) をいれる template <typename value_type = int, uint64_t ln_big = 10, uint64_t ln_sml = 4> struct CompactBitVector { private: size_t n, n_big, n_sml, n_blk, ln_blk; vector<value_type> big, sml, bit; int popcount(value_type b) const { return __builtin_popcountll(b); // GCC builtin function } void build(vector<value_type> vec); public: // 構築: O(N) CompactBitVector(); CompactBitVector(vector<value_type> vec); CompactBitVector(vector<value_type> vec, int k); // 数列のサイズ: O(1) size_t size() const; // 全体の 1 の個数: O(1) int count() const; // k 番目の値: O(1) int value(size_t k) const; // [0, k] に存在する 1 の個数: O(1) int rank(size_t k) const; // [l, r) に存在する 1 の個数: O(1) int rank(size_t l, size_t r) const; // 1 / 0 の個数 が r を超える、インデックス k 未満最小の要素を返す: O(log N) int select1(int r, int k) const; int select0(int r, int k) const; // k 番目の次に存在する 1 / 0 は何か: O(log N) int select1_nxt(size_t k) const; int select0_nxt(size_t k) const; // k 番目の前に存在する 1 / 0 は何か: O(log N) int select1_pre(size_t k) const; int select0_pre(size_t k) const; // ビットベクトルの k 番目にアクセス int at(size_t k) const; int operator[](size_t k) const; // 出力するだけ void show() const { cerr << "# big "; for(size_t i=0; i<big.size(); i++) { cerr << big[i] << " "; } cerr << endl; cerr << "# sml "; for(size_t i=0; i<sml.size(); i++) { cerr << sml[i] << " "; } cerr << endl; cerr << "# bit "; for(size_t i=0; i<bit.size(); i++) { cerr << bit[i] << " "; } cerr << endl; } }; template <typename value_type, uint64_t ln_big, uint64_t ln_sml> void CompactBitVector<value_type, ln_big, ln_sml>::build(vector<value_type> vec) { big.resize(((n + n_big - 1) >> ln_big) + 1); // O(N / log^2 N) memory sml.resize(big.size() << ln_blk); // O(N / log N) memory bit.resize(big.size() << ln_blk); // O(N / log N) memory for(size_t i=0; i<n; i++) { size_t b = i >> ln_big; big[b+1] += vec[i]; size_t s = i >> ln_sml, m = i & (n_sml - 1); sml[s] += vec[i]; bit[s] |= (static_cast<value_type>(vec[i]) << m); } // accumulate for(size_t i=1; i<big.size(); i++) big[i] += big[i-1]; for(size_t i=0; i<big.size(); i++) { for(size_t j=1; j<n_blk; j++) { sml[(i << ln_blk) + j] += sml[(i << ln_blk) + j - 1]; } } } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> CompactBitVector<value_type, ln_big, ln_sml>::CompactBitVector() {} template <typename value_type, uint64_t ln_big, uint64_t ln_sml> CompactBitVector<value_type, ln_big, ln_sml>::CompactBitVector(vector<value_type> vec) : n(vec.size()), n_big(1ULL << ln_big), n_sml(1ULL << ln_sml), n_blk(n_big >> ln_sml), ln_blk(ln_big - ln_sml) { build(vec); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> CompactBitVector<value_type, ln_big, ln_sml>::CompactBitVector(vector<value_type> vec, int k) : n(vec.size()), n_big(1ULL << ln_big), n_sml(1ULL << ln_sml), n_blk(n_big >> ln_sml), ln_blk(ln_big - ln_sml) { vector<value_type> n_vec; for(auto e : vec) n_vec.emplace_back(e >> k & 1); build(n_vec); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> size_t CompactBitVector<value_type, ln_big, ln_sml>::size() const { return n; } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::count() const { return rank(n-1); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::value(size_t k) const { if(k >= n) return 0; size_t m = k & (n_sml - 1); return bit[k >> ln_sml] >> m & 1; } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::rank(size_t k) const { if(k >= n) return 0; // for range query size_t m = k & (n_sml - 1), mask = (1ULL << n_sml) - (1ULL << (m+1)); return big[k >> ln_big] + sml[k >> ln_sml] - popcount(bit[k >> ln_sml] & mask); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::rank(size_t l, size_t r) const { if(l >= r) return 0; return rank(r-1) - rank(l-1); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::select1(int r, int k) const { int ub = n+1, lb = -1; while(ub - lb > 1) { int mid = (ub + lb) / 2; if(rank(mid) > r) ub = mid; else lb = mid; } return (ub < k) ? ub : -1; } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::select0(int r, int k) const { int ub = n+1, lb = -1; while(ub - lb > 1) { int mid = (ub + lb) / 2; if(mid + 1 - rank(mid) > r) ub = mid; else lb = mid; } return (ub < k) ? ub : -1; } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::select1_nxt(size_t k) const { return select1(rank(k), n); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::select0_nxt(size_t k) const { return select0(rank(k), n); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::select1_pre(size_t k) const { return select1(rank(k) - 1 - value(k), k); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::select0_pre(size_t k) const { return select0(rank(k) - 1 - value(k), k); } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::at(size_t k) const { return bit[k >> ln_sml] >> (k & (n_sml - 1)) & 1; } template <typename value_type, uint64_t ln_big, uint64_t ln_sml> int CompactBitVector<value_type, ln_big, ln_sml>::operator[](size_t k) const { return at(k); } #line 8 "structure/verify/verify_strc_023_compact_bitvector.cpp" int main() { int N; cin >> N; vector<int> vec(N); for(int i=0; i<N; i++) cin >> vec[i]; SuccinctBitVector<> sb(vec); for(int i=0; i<N; i++) { cout << sb.rank(i) << " "; } cout << endl; for(int i=0; i<N; i++) { int a = sb.select_nxt(i); cout << (a < 0 ? -1 : a + 1) << " "; } cout << endl; for(int i=0; i<N; i++) { int a = sb.select_pre(i); cout << (a < 0 ? -1 : a + 1) << " "; } cout << endl; cout << "count: " << sb.count() << ", size = " << sb.size() << endl; /* while(true) { int q; cin >> q; if(q == 1) { int k; cin >> k; k--; cout << sb.rank(k) << endl; } if(q == 2) { int k; cin >> k; k--; int a = sb.select_nxt(k); cout << (a < 0 ? -1 : a + 1) << endl; } if(q == 3) { int k; cin >> k; k--; int a = sb.select_pre(k); cout << (a < 0 ? -1 : a + 1) << endl; } if(q == 4) { int l, r; cin >> l >> r; l--; cout << sb.rank(l, r) << endl; } } */ return 0; }