バケット分割による区間クエリ処理
(Src/DataStructure/Bucket/BucketRangeProduct.hpp)

• View this file on GitHub
• Last update: 2026-03-26 22:26:11+09:00
• Include: #include "Src/DataStructure/Bucket/BucketRangeProduct.hpp"

minLeftだけverifyしていないです。

Depends on

• Src/Algebra/Group/GroupConcept.hpp
• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc405.test.cpp
• Test/AtCoder/arc197_c.test.cpp
• Test/AtCoder/awc0032_e.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Algebra/Group/GroupConcept.hpp"

#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <vector>

namespace zawa {

template <concepts::Monoid M>
class BucketRangeQuery {
public:

    using V = typename M::Element;

    inline usize size() const {
        return m_n;
    }

    inline usize bucketSize() const {
        return m_b;
    }

    BucketRangeQuery() = default;

    BucketRangeQuery(usize N,usize B = std::numeric_limits<usize>::max()) 
        : m_n{N},m_b{BucketSize(N,B)}, m_data(N,M::identity()), m_bucket((m_n+m_b-1)/m_b,M::identity()) {
        for (usize i = 0 ; i < size() ; i++)
            m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],m_data[i]);
    }

    BucketRangeQuery(std::vector<V> A,usize B = std::numeric_limits<usize>::max())
        : m_n{A.size()},m_b{BucketSize(A.size(),B)},m_data(std::move(A)),m_bucket((m_n+m_b-1)/m_b,M::identity()) {
        for (usize i = 0 ; i < size() ; i++)
            m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],m_data[i]);
    }

    V product(usize l,usize r) const {
        assert(l <= r and r <= size());
        V res = M::identity();
        while (l < r and l % bucketSize())
            res = M::operation(res,m_data[l++]);
        while (l + bucketSize() <= r) {
            res = M::operation(res,m_bucket[l/bucketSize()]);
            l += bucketSize();
        }
        while (l < r)
            res = M::operation(res,m_data[l++]);
        return res;
    }

    V operator[](usize i) const {
        assert(i < size());
        return m_data[i];
    }

    V bucketValue(usize i) const {
        assert(i < m_bucket.size());
        return m_bucket[i];
    }

    void assign(usize i,V x) {
        assert(i < size());
        const usize idx = i/bucketSize();
        if constexpr (concepts::Group<M>) {
            m_bucket[idx] = M::operation(m_bucket[idx],M::inverse(m_data[i]));
            m_data[i] = std::move(x);
            m_bucket[idx] = M::operation(m_bucket[idx],m_data[i]);
        }
        else {
            m_data[i] = std::move(x);
            m_bucket[idx] = M::identity();
            const usize l = idx*bucketSize(),r = std::min(size(),(idx+1)*bucketSize());
            for (usize j = l ; j < r ; j++)
                m_bucket[idx] = M::operation(m_bucket[idx],m_data[j]);
        }
    }

    void operation(usize i,V x) {
        assert(i < size());
        m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],x);
        m_data[i] = M::operation(m_data[i],x);
    }

    template <class F>
    requires std::predicate<F,V>
    usize maxRight(usize i,F f) const {
        assert(i <= size());
        assert(f(M::identity()));
        V pd = M::identity();
        while (i < size() and i % bucketSize()) {
            V nxt = M::operation(pd,m_data[i]);
            if (!f(nxt))
                return i;
            pd = std::move(nxt);
            i++;
        }
        while (i + bucketSize() <= size()) {
            V nxt = M::operation(pd,m_bucket[i/bucketSize()]);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i += bucketSize();
        }
        while (i < size()) {
            V nxt = M::operation(pd,m_data[i]);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i++;
        }
        return i;
    }

    template <class F>
    requires std::predicate<F,V>
    usize minLeft(usize i,F f) const {
        assert(i <= size());
        assert(f(M::identity()));
        V pd = M::identity();
        while (i % bucketSize()) {
            V nxt = M::operation(m_data[i-1],pd);
            if (!f(nxt))
                return i;
            pd = std::move(nxt);
            i--;
        }
        while (i) {
            V nxt = M::operation(m_bucket[i/bucketSize()-1],pd);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i -= bucketSize();
        }
        while (i) {
            V nxt = M::operation(m_data[i-1],pd);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i--;
        }
        return i;
    }

private:

    usize m_n,m_b;

    std::vector<V> m_data,m_bucket;

    static usize BucketSize(usize N,usize B) {
        return B == std::numeric_limits<usize>::max() ? std::max<usize>(1,sqrtl(N)) : B;
    }
};


} // namespace zawa

#line 2 "Src/DataStructure/Bucket/BucketRangeProduct.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/Bucket/BucketRangeProduct.hpp"

#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <vector>

namespace zawa {

template <concepts::Monoid M>
class BucketRangeQuery {
public:

    using V = typename M::Element;

    inline usize size() const {
        return m_n;
    }

    inline usize bucketSize() const {
        return m_b;
    }

    BucketRangeQuery() = default;

    BucketRangeQuery(usize N,usize B = std::numeric_limits<usize>::max()) 
        : m_n{N},m_b{BucketSize(N,B)}, m_data(N,M::identity()), m_bucket((m_n+m_b-1)/m_b,M::identity()) {
        for (usize i = 0 ; i < size() ; i++)
            m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],m_data[i]);
    }

    BucketRangeQuery(std::vector<V> A,usize B = std::numeric_limits<usize>::max())
        : m_n{A.size()},m_b{BucketSize(A.size(),B)},m_data(std::move(A)),m_bucket((m_n+m_b-1)/m_b,M::identity()) {
        for (usize i = 0 ; i < size() ; i++)
            m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],m_data[i]);
    }

    V product(usize l,usize r) const {
        assert(l <= r and r <= size());
        V res = M::identity();
        while (l < r and l % bucketSize())
            res = M::operation(res,m_data[l++]);
        while (l + bucketSize() <= r) {
            res = M::operation(res,m_bucket[l/bucketSize()]);
            l += bucketSize();
        }
        while (l < r)
            res = M::operation(res,m_data[l++]);
        return res;
    }

    V operator[](usize i) const {
        assert(i < size());
        return m_data[i];
    }

    V bucketValue(usize i) const {
        assert(i < m_bucket.size());
        return m_bucket[i];
    }

    void assign(usize i,V x) {
        assert(i < size());
        const usize idx = i/bucketSize();
        if constexpr (concepts::Group<M>) {
            m_bucket[idx] = M::operation(m_bucket[idx],M::inverse(m_data[i]));
            m_data[i] = std::move(x);
            m_bucket[idx] = M::operation(m_bucket[idx],m_data[i]);
        }
        else {
            m_data[i] = std::move(x);
            m_bucket[idx] = M::identity();
            const usize l = idx*bucketSize(),r = std::min(size(),(idx+1)*bucketSize());
            for (usize j = l ; j < r ; j++)
                m_bucket[idx] = M::operation(m_bucket[idx],m_data[j]);
        }
    }

    void operation(usize i,V x) {
        assert(i < size());
        m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],x);
        m_data[i] = M::operation(m_data[i],x);
    }

    template <class F>
    requires std::predicate<F,V>
    usize maxRight(usize i,F f) const {
        assert(i <= size());
        assert(f(M::identity()));
        V pd = M::identity();
        while (i < size() and i % bucketSize()) {
            V nxt = M::operation(pd,m_data[i]);
            if (!f(nxt))
                return i;
            pd = std::move(nxt);
            i++;
        }
        while (i + bucketSize() <= size()) {
            V nxt = M::operation(pd,m_bucket[i/bucketSize()]);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i += bucketSize();
        }
        while (i < size()) {
            V nxt = M::operation(pd,m_data[i]);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i++;
        }
        return i;
    }

    template <class F>
    requires std::predicate<F,V>
    usize minLeft(usize i,F f) const {
        assert(i <= size());
        assert(f(M::identity()));
        V pd = M::identity();
        while (i % bucketSize()) {
            V nxt = M::operation(m_data[i-1],pd);
            if (!f(nxt))
                return i;
            pd = std::move(nxt);
            i--;
        }
        while (i) {
            V nxt = M::operation(m_bucket[i/bucketSize()-1],pd);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i -= bucketSize();
        }
        while (i) {
            V nxt = M::operation(m_data[i-1],pd);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i--;
        }
        return i;
    }

private:

    usize m_n,m_b;

    std::vector<V> m_data,m_bucket;

    static usize BucketSize(usize N,usize B) {
        return B == std::numeric_limits<usize>::max() ? std::max<usize>(1,sqrtl(N)) : B;
    }
};


} // namespace zawa

Back to top page