c++ sparsetable 模版

server/2024/10/18 5:53:33/

闭区间查询

支持
区间最大
区间最小
区间和
区间最大下标
区间最小下标

#include <bits/stdc++.h>
using namespace std;#ifndef NO_UNIQUE_ADDRESS
#    ifdef __has_cpp_attribute
#        if __has_cpp_attribute(no_unique_address)
#            define NO_UNIQUE_ADDRESS [[no_unique_address]]
#        endif
#    endif
#    ifndef NO_UNIQUE_ADDRESS
#        define NO_UNIQUE_ADDRESS
#    endif
#endif // !NO_UNIQUE_ADDRESSnamespace details {inline unsigned int bsf32(uint32_t n) noexcept {
#if defined __GNUC__return __builtin_ctz(n);
#elif defined _MSC_VERunsigned long ans;_BitScanForward(&ans, n);return ans;
#elifstatic constexpr unsigned char table[32] = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,};return table[((n & -n) * 0x077CB531) >> 57];
#endif}inline unsigned int bsf64(uint64_t n) noexcept {
#if defined __GNUC__return __builtin_ctzll(n);
#elif defined _MSC_VERunsigned long ans;_BitScanForward64(&ans, n);return ans;
#elifstatic constexpr unsigned char table[64] = {0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,};return table[((n & -n) * 0x03f79d71b4ca8b09) >> 58];
#endif}inline unsigned int bsr32(uint32_t n) noexcept {
#if defined __GNUC__return 31 - __builtin_clz(n);
#elif defined _MSC_VERunsigned long ans;_BitScanReverse(&ans, n);return ans;
#eliffloat t = n;uint32_t ans;memcpy(&ans, &t, sizeof(float));return (ans >> 23 & 255) - 127;
#endif}inline unsigned int bsr64(uint64_t n) noexcept {
#if defined __GNUC__return 63 - __builtin_clzll(n);
#elif defined _MSC_VERunsigned long ans;_BitScanReverse64(&ans, n);return ans;
#eliffloat t = n;uint32_t ans;memcpy(&ans, &t, sizeof(float));return (ans >> 23 & 255) - 127;
#endif}inline unsigned int popcnt32(uint32_t n) noexcept {
#if defined __GNUC__return __builtin_popcount(n);
#elif defined _MSC_VERreturn __popcnt(n);
#elifn -= ((n >> 1) & 0x55555555);n = (n & 0x33333333) + ((n >> 2) & 0x33333333);return ((((n >> 4) + n) & 0x0f0f0f0f) * 0x01010101) >> 24;
#endif}inline unsigned int popcnt64(uint64_t n) noexcept {
#if defined __GNUC__return __builtin_popcountll(n);
#elif defined _MSC_VERreturn __popcnt64(n);
#elifn -= ((n >> 1) & 0x5555555555555555);n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);return ((((n >> 4) + n) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101) >> 56;
#endif}inline unsigned int parity32(uint32_t n) noexcept {
#if defined __GNUC__return __builtin_parity(n);
#elif defined _MSC_VERreturn __popcnt(n) & 1;
#elifn ^= n >> 1;n ^= n >> 2;n = (n & 0x11111111) * 0x11111111;return (n >> 28) & 1;
#endif}inline unsigned int parity64(uint64_t n) noexcept {
#if defined __GNUC__return __builtin_parityll(n);
#elif defined _MSC_VERreturn __popcnt64(n) & 1;
#elifn ^= n >> 1;n ^= n >> 2;n = (n & 0x1111111111111111) * 0x1111111111111111;return (n >> 60) & 1;
#endif}template<typename I, bool B = 32 < std::numeric_limits<I>::digits>struct _BitFuncImpl {inline static unsigned int bsf(I n) noexcept { return bsf64(n); }inline static unsigned int bsr(I n) noexcept { return bsr64(n); }inline static unsigned int popcnt(I n) noexcept { return popcnt64(n); }inline static unsigned int parity(I n) noexcept { return parity64(n); }};template<typename I>struct _BitFuncImpl<I, false> {inline static unsigned int bsf(I n) noexcept { return bsf32(n); }inline static unsigned int bsr(I n) noexcept { return bsr32(n); }inline static unsigned int popcnt(I n) noexcept { return popcnt32(n); }inline static unsigned int parity(I n) noexcept { return parity32(n); }};template<typename I>inline unsigned int bsf(I n) noexcept { return _BitFuncImpl<I>::bsf(n); }template<typename I>inline unsigned int bsr(I n) noexcept { return _BitFuncImpl<I>::bsr(n); }template<typename I>inline unsigned int popcnt(I n) noexcept { return _BitFuncImpl<I>::popcnt(n); }template<typename I>inline unsigned int parity(I n) noexcept { return _BitFuncImpl<I>::parity(n); }template<typename T, size_t K = 0, bool = std::is_empty<T>::value && !std::is_final<T>::value>struct Derivable {private:T val;public:constexpr Derivable() = default;template<typename... Args>constexpr Derivable(Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value) : val(std::forward<Args>(args)...) {}inline constexpr T& value() noexcept { return val; }inline constexpr const T& value() const noexcept { return val; }};template<typename T, size_t K>struct Derivable<T, K, true> : private T {constexpr Derivable() = default;template<typename... Args>constexpr Derivable(Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value) : T(std::forward<Args>(args)...) {}inline constexpr T& value() noexcept { return *this; }inline constexpr const T& value() const noexcept { return *this; }};template<typename Alloc>struct InitializerIterator {using traits = std::allocator_traits<Alloc>;using pointer = typename traits::pointer;using value_type = typename traits::value_type;InitializerIterator(const InitializerIterator&) = delete;InitializerIterator(InitializerIterator&& other) noexcept: ptr(other.ptr), cur(other.cur), p_alloc(other.p_alloc){other.ptr = other.cur = nullptr;other.p_alloc = nullptr;}InitializerIterator(pointer ptr, Alloc& alloc) noexcept : ptr(ptr), cur(ptr), p_alloc(&alloc) {}~InitializerIterator() noexcept {if (!std::is_trivially_destructible<value_type>::value)for (pointer it = ptr;it != cur;++it)traits::destroy(*p_alloc, std::addressof(*it));}inline pointer release() noexcept {return ptr = cur;}inline InitializerIterator& operator*() noexcept { return *this; }inline InitializerIterator& operator++() noexcept { return *this; }inline InitializerIterator& operator++(int) noexcept { return *this;  }InitializerIterator& operator=(const InitializerIterator&) = delete;InitializerIterator& operator=(InitializerIterator&& other) noexcept {ptr = other.ptr;cur = other.cur;p_alloc = other.p_alloc;other.ptr = other.cur = nullptr;other.p_alloc = nullptr;return *this;}template<typename T>inline InitializerIterator& operator=(T&& val) noexcept(noexcept(std::is_nothrow_constructible<value_type, T&&>::value)) {traits::construct(*p_alloc, std::addressof(*cur), std::forward<T>(val));++cur;return *this;}private:pointer ptr, cur;Alloc* p_alloc;};
}template<typename TableIt, typename OutIt, typename Op>
inline OutIt make_sparse_table(TableIt st, size_t n, OutIt it, const Op& op = {}) {TableIt pre = std::move(st);for (size_t i = 2;i <= n;i *= 2) {for (size_t j = 0;j <= n - i;++j)*it++ = op(pre[j], pre[j + i / 2]);pre += n + 1 - i / 2;}return std::move(it);
}inline size_t sparse_table_size(size_t n) {const size_t h = details::bsr(n) + size_t(1);return n * h + h + size_t(1) - (size_t(1) << h);
}template<typename TableIt, typename Op>
inline typename std::iterator_traits<TableIt>::value_type query_sparse_table(TableIt st, size_t n, size_t l, size_t r, const Op& op = {}) {assert(l <= r && r < n);r++;const size_t h = details::bsr(r - l), ph = size_t(1) << h;const auto row = st + (n * h + h + 1 - ph);return op(row[l], row[r - ph]);
}template<typename It, typename Op>
class SparseTableView {
public:using value_type = typename std::iterator_traits<It>::value_type;using size_type = unsigned;using operator_type = Op;protected:It st;size_type n;NO_UNIQUE_ADDRESS operator_type op;public:SparseTableView(It it, size_type n, const operator_type& op = {}) : st(std::move(it)), n(n), op(op) {}inline size_type size() const noexcept {return n;}// 闭区间inline value_type query(size_type l, size_type r) const {return query_sparse_table(st, n, l, r, op);}// 闭区间inline value_type query(size_type l, size_type r, const value_type& unitary) const {return r <= l ? unitary : query(l, r);}
};template<typename T, typename Op>
class SparseTable : protected SparseTableView<T*, Op> {
private:using base_type = SparseTableView<T*, Op>;public:using typename base_type::value_type;using typename base_type::size_type;using typename base_type::operator_type;using pointer = value_type*;using reference = value_type&;using const_pointer = const value_type*;using const_reference = const value_type&;private:using allocator_type = std::allocator<value_type>;using allocator_traits = std::allocator_traits<allocator_type>;inline const operator_type& operator_() const noexcept {return this->op;}inline static allocator_type& allocator() noexcept {static allocator_type alloc{};return alloc;}struct Guard {pointer ptr;size_type len;~Guard() { if (len > 0) allocator_traits::deallocate(allocator(), ptr, len); }};inline void clean() noexcept {if (this->n > 0) {const size_type st_size = sparse_table_size(this->n);if (!std::is_trivially_destructible<value_type>::value) {const pointer end = this->st + st_size;for (pointer it = this->st;it != end;++it)allocator_traits::destroy(allocator(), it);}allocator_traits::deallocate(allocator(), this->st, st_size);}}public:template<typename It>SparseTable(It it, size_type n, const Op& op = {}): base_type(nullptr, n, op){if (n == 0) return;const size_type st_size = sparse_table_size(n);Guard guard = {allocator_traits::allocate(allocator(), st_size), st_size};details::InitializerIterator<allocator_type> initializer(guard.ptr, allocator());for (size_type i = 0;i < n;++i, ++it)*initializer++ = *it;make_sparse_table(guard.ptr, n, std::move(initializer), operator_()).release();this->st = guard.ptr;guard.len = 0;}template<typename S>SparseTable(const S& seq, const Op& op = {}) : SparseTable(seq.begin(), seq.size(), op) {}SparseTable(const SparseTable&) = delete;SparseTable(SparseTable&& other) noexcept: base_type(std::move(other)){other.st = nullptr;other.n = 0;}SparseTable& operator=(const SparseTable&) = delete;SparseTable& operator=(SparseTable&& other) noexcept {clean();base_type::operator=(std::move(other));other.st = nullptr;other.n = 0;return *this;}~SparseTable() {clean();}inline void clear() noexcept {clean();this->st = nullptr;this->n = 0;}inline SparseTableView<const_pointer, Op> view() const {return SparseTableView<const_pointer, Op>(this->st, this->n, this->op);}using base_type::size;using base_type::query;
};class Solution {
public:struct MAX {int operator()(int x, int y) const noexcept {return std::max(x, y);}};vector<int> maxSlidingWindow(vector<int>& nums, int k) {SparseTable<int, MAX> st(nums);vector<int> ans;for (size_t i = 0, n = nums.size(); i + k <= n; ++i)ans.push_back(st.query(i, i + k - 1)); // 调整为闭区间return ans;}
};template<typename T>
struct MAX {T operator()(T x, T y) const noexcept {return std::max(x, y);}
};template<typename T>
struct MIN {T operator()(T x, T y) const noexcept {return std::min(x, y);}
};template<typename T>
struct SUM {T operator()(T x, T y) const noexcept {return x + y;}
};struct MaxIndex {const vector<int>& nums;MaxIndex(const vector<int>& nums) : nums(nums) {}int operator()(int i, int j) const noexcept {return nums[i] >= nums[j] ? i : j;}
};struct MinIndex {const vector<int>& nums;MinIndex(const vector<int>& nums) : nums(nums) {}int operator()(int i, int j) const noexcept {return nums[i] <= nums[j] ? i : j;}
};template<typename T>
struct SparseTableMaxIndex {MaxIndex max_index;vector<int> indices;SparseTable<T, MaxIndex> max_st;SparseTableMaxIndex(const vector<int>& nums) : max_index(nums), indices(nums.size()),max_st((iota(indices.begin(), indices.end(), 0), indices), max_index) {}T query(int l, int r) const {return max_st.query(l, r);}
};template<typename T>
struct SparseTableMinIndex {MinIndex min_index;vector<int> indices;SparseTable<T, MinIndex> min_st;SparseTableMinIndex(const vector<int>& nums) : min_index(nums), indices(nums.size()),min_st((iota(indices.begin(), indices.end(), 0), indices), min_index) {}T query(int l, int r) const {return min_st.query(l, r);}
};template<typename T>
using SparseTableSum = SparseTable<T, SUM<T>>;template<typename T>
using SparseTableMax = SparseTable<T, MAX<T>>;template<typename T>
using SparseTableMin = SparseTable<T, MIN<T>>;int main() {vector<int> nums = {1, -1, 4, 7};// 闭区间查询SparseTableMaxIndex<int> st(nums);for (int i = 0; i < 4; i++) {for (int j = i; j <= 4; j++) {cout << st.query(i, j) << " "; // 调整为闭区间}cout << endl;}
}
#include <bits/stdc++.h>
using namespace std;#ifndef NO_UNIQUE_ADDRESS
#    ifdef __has_cpp_attribute
#        if __has_cpp_attribute(no_unique_address)
#            define NO_UNIQUE_ADDRESS [[no_unique_address]]
#        endif
#    endif
#    ifndef NO_UNIQUE_ADDRESS
#        define NO_UNIQUE_ADDRESS
#    endif
#endif // !NO_UNIQUE_ADDRESSnamespace details {inline unsigned int bsf32(uint32_t n) noexcept {
#if defined __GNUC__return __builtin_ctz(n);
#elif defined _MSC_VERunsigned long ans;_BitScanForward(&ans, n);return ans;
#elifstatic constexpr unsigned char table[32] = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,};return table[((n & -n) * 0x077CB531) >> 57];
#endif}inline unsigned int bsf64(uint64_t n) noexcept {
#if defined __GNUC__return __builtin_ctzll(n);
#elif defined _MSC_VERunsigned long ans;_BitScanForward64(&ans, n);return ans;
#elifstatic constexpr unsigned char table[64] = {0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,};return table[((n & -n) * 0x03f79d71b4ca8b09) >> 58];
#endif}inline unsigned int bsr32(uint32_t n) noexcept {
#if defined __GNUC__return 31 - __builtin_clz(n);
#elif defined _MSC_VERunsigned long ans;_BitScanReverse(&ans, n);return ans;
#eliffloat t = n;uint32_t ans;memcpy(&ans, &t, sizeof(float));return (ans >> 23 & 255) - 127;
#endif}inline unsigned int bsr64(uint64_t n) noexcept {
#if defined __GNUC__return 63 - __builtin_clzll(n);
#elif defined _MSC_VERunsigned long ans;_BitScanReverse64(&ans, n);return ans;
#eliffloat t = n;uint32_t ans;memcpy(&ans, &t, sizeof(float));return (ans >> 23 & 255) - 127;
#endif}inline unsigned int popcnt32(uint32_t n) noexcept {
#if defined __GNUC__return __builtin_popcount(n);
#elif defined _MSC_VERreturn __popcnt(n);
#elifn -= ((n >> 1) & 0x55555555);n = (n & 0x33333333) + ((n >> 2) & 0x33333333);return ((((n >> 4) + n) & 0x0f0f0f0f) * 0x01010101) >> 24;
#endif}inline unsigned int popcnt64(uint64_t n) noexcept {
#if defined __GNUC__return __builtin_popcountll(n);
#elif defined _MSC_VERreturn __popcnt64(n);
#elifn -= ((n >> 1) & 0x5555555555555555);n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);return ((((n >> 4) + n) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101) >> 56;
#endif}inline unsigned int parity32(uint32_t n) noexcept {
#if defined __GNUC__return __builtin_parity(n);
#elif defined _MSC_VERreturn __popcnt(n) & 1;
#elifn ^= n >> 1;n ^= n >> 2;n = (n & 0x11111111) * 0x11111111;return (n >> 28) & 1;
#endif}inline unsigned int parity64(uint64_t n) noexcept {
#if defined __GNUC__return __builtin_parityll(n);
#elif defined _MSC_VERreturn __popcnt64(n) & 1;
#elifn ^= n >> 1;n ^= n >> 2;n = (n & 0x1111111111111111) * 0x1111111111111111;return (n >> 60) & 1;
#endif}template<typename I, bool B = 32 < std::numeric_limits<I>::digits>struct _BitFuncImpl {inline static unsigned int bsf(I n) noexcept { return bsf64(n); }inline static unsigned int bsr(I n) noexcept { return bsr64(n); }inline static unsigned int popcnt(I n) noexcept { return popcnt64(n); }inline static unsigned int parity(I n) noexcept { return parity64(n); }};template<typename I>struct _BitFuncImpl<I, false> {inline static unsigned int bsf(I n) noexcept { return bsf32(n); }inline static unsigned int bsr(I n) noexcept { return bsr32(n); }inline static unsigned int popcnt(I n) noexcept { return popcnt32(n); }inline static unsigned int parity(I n) noexcept { return parity32(n); }};template<typename I>inline unsigned int bsf(I n) noexcept { return _BitFuncImpl<I>::bsf(n); }template<typename I>inline unsigned int bsr(I n) noexcept { return _BitFuncImpl<I>::bsr(n); }template<typename I>inline unsigned int popcnt(I n) noexcept { return _BitFuncImpl<I>::popcnt(n); }template<typename I>inline unsigned int parity(I n) noexcept { return _BitFuncImpl<I>::parity(n); }template<typename T, size_t K = 0, bool = std::is_empty<T>::value && !std::is_final<T>::value>struct Derivable {private:T val;public:constexpr Derivable() = default;template<typename... Args>constexpr Derivable(Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value) : val(std::forward<Args>(args)...) {}inline constexpr T& value() noexcept { return val; }inline constexpr const T& value() const noexcept { return val; }};template<typename T, size_t K>struct Derivable<T, K, true> : private T {constexpr Derivable() = default;template<typename... Args>constexpr Derivable(Args&&... args) noexcept(std::is_nothrow_constructible<T, Args&&...>::value) : T(std::forward<Args>(args)...) {}inline constexpr T& value() noexcept { return *this; }inline constexpr const T& value() const noexcept { return *this; }};template<typename Alloc>struct InitializerIterator {using traits = std::allocator_traits<Alloc>;using pointer = typename traits::pointer;using value_type = typename traits::value_type;InitializerIterator(const InitializerIterator&) = delete;InitializerIterator(InitializerIterator&& other) noexcept: ptr(other.ptr), cur(other.cur), p_alloc(other.p_alloc){other.ptr = other.cur = nullptr;other.p_alloc = nullptr;}InitializerIterator(pointer ptr, Alloc& alloc) noexcept : ptr(ptr), cur(ptr), p_alloc(&alloc) {}~InitializerIterator() noexcept {if (!std::is_trivially_destructible<value_type>::value)for (pointer it = ptr;it != cur;++it)traits::destroy(*p_alloc, std::addressof(*it));}inline pointer release() noexcept {return ptr = cur;}inline InitializerIterator& operator*() noexcept { return *this; }inline InitializerIterator& operator++() noexcept { return *this; }inline InitializerIterator& operator++(int) noexcept { return *this;  }InitializerIterator& operator=(const InitializerIterator&) = delete;InitializerIterator& operator=(InitializerIterator&& other) noexcept {ptr = other.ptr;cur = other.cur;p_alloc = other.p_alloc;other.ptr = other.cur = nullptr;other.p_alloc = nullptr;return *this;}template<typename T>inline InitializerIterator& operator=(T&& val) noexcept(noexcept(std::is_nothrow_constructible<value_type, T&&>::value)) {traits::construct(*p_alloc, std::addressof(*cur), std::forward<T>(val));++cur;return *this;}private:pointer ptr, cur;Alloc* p_alloc;};
}template<typename TableIt, typename OutIt, typename Op>
inline OutIt make_sparse_table(TableIt st, size_t n, OutIt it, const Op& op = {}) {TableIt pre = std::move(st);for (size_t i = 2;i <= n;i *= 2) {for (size_t j = 0;j <= n - i;++j)*it++ = op(pre[j], pre[j + i / 2]);pre += n + 1 - i / 2;}return std::move(it);
}inline size_t sparse_table_size(size_t n) {const size_t h = details::bsr(n) + size_t(1);return n * h + h + size_t(1) - (size_t(1) << h);
}template<typename TableIt, typename Op>
inline typename std::iterator_traits<TableIt>::value_type query_sparse_table(TableIt st, size_t n, size_t l, size_t r, const Op& op = {}) {const size_t h = details::bsr(r - l), ph = size_t(1) << h;const auto row = st + (n * h + h + 1 - ph);return op(row[l], row[r - ph]);
}template<typename It, typename Op>
class SparseTableView {
public:using value_type = typename std::iterator_traits<It>::value_type;using size_type = unsigned;using operator_type = Op;protected:It st;size_type n;NO_UNIQUE_ADDRESS operator_type op;public:SparseTableView(It it, size_type n, const operator_type& op = {}) : st(std::move(it)), n(n), op(op) {}inline size_type size() const noexcept {return n;}inline value_type query(size_type l, size_type r) const {return query_sparse_table(st, n, l, r, op);}inline value_type query(size_type l, size_type r, const value_type& unitary) const {return r <= l ? unitary : query(l, r);}
};template<typename T, typename Op>
class SparseTable : protected SparseTableView<T*, Op> {
private:using base_type = SparseTableView<T*, Op>;public:using typename base_type::value_type;using typename base_type::size_type;using typename base_type::operator_type;using pointer = value_type*;using reference = value_type&;using const_pointer = const value_type*;using const_reference = const value_type&;private:using allocator_type = std::allocator<value_type>;using allocator_traits = std::allocator_traits<allocator_type>;inline const operator_type& operator_() const noexcept {return this->op;}inline static allocator_type& allocator() noexcept {static allocator_type alloc{};return alloc;}struct Guard {pointer ptr;size_type len;~Guard() { if (len > 0) allocator_traits::deallocate(allocator(), ptr, len); }};inline void clean() noexcept {if (this->n > 0) {const size_type st_size = sparse_table_size(this->n);if (!std::is_trivially_destructible<value_type>::value) {const pointer end = this->st + st_size;for (pointer it = this->st;it != end;++it)allocator_traits::destroy(allocator(), it);}allocator_traits::deallocate(allocator(), this->st, st_size);}}public:template<typename It>SparseTable(It it, size_type n, const Op& op = {}): base_type(nullptr, n, op){if (n == 0) return;const size_type st_size = sparse_table_size(n);Guard guard = {allocator_traits::allocate(allocator(), st_size), st_size};details::InitializerIterator<allocator_type> initializer(guard.ptr, allocator());for (size_type i = 0;i < n;++i, ++it)*initializer++ = *it;make_sparse_table(guard.ptr, n, std::move(initializer), operator_()).release();this->st = guard.ptr;guard.len = 0;}template<typename S>SparseTable(const S& seq, const Op& op = {}) : SparseTable(seq.begin(), seq.size(), op) {}SparseTable(const SparseTable&) = delete;SparseTable(SparseTable&& other) noexcept: base_type(std::move(other)){other.st = nullptr;other.n = 0;}SparseTable& operator=(const SparseTable&) = delete;SparseTable& operator=(SparseTable&& other) noexcept {clean();base_type::operator=(std::move(other));other.st = nullptr;other.n = 0;return *this;}~SparseTable() {clean();}inline void clear() noexcept {clean();this->st = nullptr;this->n = 0;}inline SparseTableView<const_pointer, Op> view() const {return SparseTableView<const_pointer, Op>(this->st, this->n, this->op);}using base_type::size;using base_type::query;
};

http://www.ppmy.cn/server/132694.html

相关文章

Maximo Automation Script导出与使用

Maximo Automation Script导出与使用

以前的文章介绍了 Automation Script 的使用&#xff0c;以及 Automation Script 之间如何调用。今天换一种方法看看怎样在 Automation Script 中导出和使用函数和对象。 函数导出与调用 创建 Automation Script 库 MYLIB&#xff0c;内容如下&#xff1a; function func1()…
阅读更多...
阿里 C++面试，算法题没做出来，，，

阿里 C++面试，算法题没做出来，，，

我本人是非科班学 C 后端和嵌入式的。在我面试的过程中&#xff0c;竟然得到了阿里​ C 研发工程师的面试机会。因为&#xff0c;阿里主要是用 Java 比较多&#xff0c;C 的岗位比较少​&#xff0c;所以感觉这个机会还是挺难得的。 阿里 C 研发工程师面试考了我一道类似于快速…
阅读更多...
shell脚本使用总结

shell脚本使用总结

shell脚本功能总结 总的可以分为三大类: 机器相关 状态 ping监控 成功率平均响应时间(延迟) roothcss-ecs-c2b8:~# ping localhost PING localhost (127.0.0.1) 56(84) bytes of data. 64 bytes from localhost (127.0.0.1): icmp_seq1 ttl64 time0.044 ms 64 bytes from loca…
阅读更多...
【Linux】常见指令（下）

【Linux】常见指令（下）

新建会话 本文中所有的指令都会在普通用户中进行介绍&#xff0c;而非root账号&#xff0c;这是由于root账户在进行部分指令的同时并不会出现警告&#xff0c;影响操作。在root账户下新建普通用户的方法在前文中已经有展示&#xff0c;这里不做介绍。 这里首先会介绍如何在xsh…
阅读更多...
请求的响应----状态码分为五大类(爬虫)

请求的响应----状态码分为五大类(爬虫)

前言 一个爬虫的成功与否&#xff0c;在于你是否拿到了想要的数据&#xff1b;一个请求的成功与否&#xff0c;在于响应的状态码&#xff0c;它标明了当前请求下这个响应的结果&#xff0c;是好还是坏。上节课程学习了HTTPS和HTTP协议的各自优势&#xff0c;本节课程进入到请求…
阅读更多...
【二刷hot-100】day2

【二刷hot-100】day2

目录 1.无重复字符的最长子串 2.找到字符串中所有字母异位词 3.和为 K 的子数组 4.滑动窗口最大值 1.无重复字符的最长子串 class Solution {public int lengthOfLongestSubstring(String s) {Map<Character,Integer> dict new HashMap<>();int ret0;int i-1;for…
阅读更多...
设计模式和软件框架的关系

设计模式和软件框架的关系

设计模式和软件框架在软件开发中都有助于解决复杂问题和提高代码质量&#xff0c;但它们在概念和使用上存在一些区别。它们的关系可以通过以下几点理解&#xff1a; 层次与抽象程度 设计模式&#xff08;Design Patterns&#xff09;是一组通用的、可复用的解决方案&#xff0c…
阅读更多...
除GOF23种设计模式之简单工厂模式

除GOF23种设计模式之简单工厂模式

文章目录 1. 简介2. 代码2.1 抽象类&#xff1a;Course.java2.2 产品A:JavaCourse.java2.3 产品B:PythonCourse.java2.4 工厂:CourseFactory.java2.5 测试&#xff1a;Test.java 3. 心得参考链接&#xff08;无&#xff09; 1. 简介 简单工厂模式(Simple Factory Patern):又称…
阅读更多...
最新文章

Copyright @ 2022~2023