This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#include "sparse_table/disjoint_sparse_table.hpp"
#ifndef DISJOINT_SPARSE_TABLE_HPP #define DISJOINT_SPARSE_TABLE_HPP #include <cassert> #include <vector> #include "../bit/ctz.hpp" #include "../bit/msb.hpp" //=== template <class SemiGroup> struct DisjointSparseTable { using T = typename SemiGroup::value_type; using G = SemiGroup; std::vector<std::vector<T>> table; DisjointSparseTable() = default; template <class InputItr> DisjointSparseTable(InputItr first, InputItr last) { build(first, last); }; template <class InputItr> void build(InputItr first, InputItr last) { int n = std::distance(first, last); int logn = 1; while ((1 << logn) < n) logn++; table.reserve(logn); table.emplace_back(first, last); for (int i = 1; i < logn; i++) { table.emplace_back(first, last); int w = 1 << i; for (int k = w; k < n; k += 2 * w) { for (int j = k - 2; j >= k - w; j--) { table[i][j] = G::operation(table[i][j], table[i][j + 1]); } for (int j = k + 1; j < std::min(n, k + w); j++) { table[i][j] = G::operation(table[i][j], table[i][j - 1]); } } } }; // [l, r) T fold(int l, int r) { assert(l < r); assert(l >= 0 && r <= size()); r--; int x = l ^ r; if (x == 0) return table[0][l]; else return G::operation(table[ctz32(msb32(x))][l], table[ctz32(msb32(x))][r]); }; T fold(int l, int r, SemiGroup e) { if (l >= r) return e; return fold(l, r); }; int size() { return table[0].size(); }; const T operator[](int k) { return fold(k, k + 1); }; }; //=== #endif
#line 1 "sparse_table/disjoint_sparse_table.hpp" #include <cassert> #include <vector> #line 1 "bit/ctz.hpp" #include <cstdint> inline int ctz32_(uint32_t bit) { static const int table[] = { 0, 1, 2, 6, 3, 11, 7, 16, 4, 14, 12, 21, 8, 23, 17, 26, 31, 5, 10, 15, 13, 20, 22, 25, 30, 9, 19, 24, 29, 18, 28, 27, }; static const uint32_t de_bruijn = 0x04653adf; bit &= ~bit + 1; return table[(bit * de_bruijn) >> 27]; }; inline int ctz32(uint32_t bit) { if (bit == 0) return 32; #ifdef __has_builtin return __builtin_ctz(bit); #else return ctz32_(bit); #endif }; inline int ctz64_(uint64_t bit) { static const int table[] = { 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58, }; static const uint64_t de_bruijn = 0x0218a392cd3d5dbfull; bit &= ~bit + 1; return table[(bit * de_bruijn) >> 58]; }; inline int ctz64(uint64_t bit) { if (bit == 0) return 64; #ifdef __has_builtin return __builtin_ctzll(bit); #else return ctz64_(bit); #endif }; #line 1 "bit/msb.hpp" #line 5 "bit/msb.hpp" inline uint32_t msb32_(uint32_t bit) { bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; return bit ^ (bit >> 1); }; inline uint32_t msb32(uint32_t x) { if (x == 0) return 0; #ifdef __has_builtin return 1u << (31 - __builtin_clz(x)); #else return msb32_(x); #endif }; inline uint64_t msb64_(uint64_t bit) { bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; bit |= bit >> 32; return bit ^ (bit >> 1); }; inline uint64_t msb64(uint64_t x) { if (x == 0) return 0; #ifdef __has_builtin return 1ull << (63 - __builtin_clzll(x)); #else return msb64_(x); #endif }; #line 9 "sparse_table/disjoint_sparse_table.hpp" //=== template <class SemiGroup> struct DisjointSparseTable { using T = typename SemiGroup::value_type; using G = SemiGroup; std::vector<std::vector<T>> table; DisjointSparseTable() = default; template <class InputItr> DisjointSparseTable(InputItr first, InputItr last) { build(first, last); }; template <class InputItr> void build(InputItr first, InputItr last) { int n = std::distance(first, last); int logn = 1; while ((1 << logn) < n) logn++; table.reserve(logn); table.emplace_back(first, last); for (int i = 1; i < logn; i++) { table.emplace_back(first, last); int w = 1 << i; for (int k = w; k < n; k += 2 * w) { for (int j = k - 2; j >= k - w; j--) { table[i][j] = G::operation(table[i][j], table[i][j + 1]); } for (int j = k + 1; j < std::min(n, k + w); j++) { table[i][j] = G::operation(table[i][j], table[i][j - 1]); } } } }; // [l, r) T fold(int l, int r) { assert(l < r); assert(l >= 0 && r <= size()); r--; int x = l ^ r; if (x == 0) return table[0][l]; else return G::operation(table[ctz32(msb32(x))][l], table[ctz32(msb32(x))][r]); }; T fold(int l, int r, SemiGroup e) { if (l >= r) return e; return fold(l, r); }; int size() { return table[0].size(); }; const T operator[](int k) { return fold(k, k + 1); }; }; //===