区間 chmin クエリ solver (Range ChangeMin Query Solver)
(src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp)

View this file on GitHub
Last update: 2023-08-18 19:53:37+09:00
Include: #include "src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp"

数列に対する区間chminクエリを処理するデータ構造。

内部ではセグメント木を用いているため、詳細な仕様などはそちらのドキュメントに追従する。

コンストラクタ

(1) RangeChminQuerySolver< T >(usize n)
(2) RangeChminQuerySolver< T >(usize n, T v)
(3) RangeChminQuerySolver< T >(std::vector< T > vs)

Depends on

Verified with

test/atcoder/abc179_f/range-chmin.test.cpp

Code

#pragma once

#include "src/data-structure/segment-tree/presets/monoid/operator-structure-chmin.hpp"
#include "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"

namespace luz {

  template < typename T >
  using RangeChminQuerySolver =
      DualSegmentTree< monoid::RangeChminQueryMonoid< T > >;

} // namespace luz

#line 2 "src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp"

#line 2 "src/data-structure/segment-tree/presets/monoid/operator-structure-chmin.hpp"

#include <algorithm>
#include <limits>

namespace luz::monoid {

  template < typename T >
  class RangeChminQueryMonoid {
    static constexpr T identity_{std::numeric_limits< T >::max()};

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return std::min(a, b);
    }

    static constexpr T identity() {
      return identity_;
    }
  };

} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#line 6 "src/cpp-template/header/rep.hpp"

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/utility/bit/bit-width.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

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

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/utility/bit/popcount.hpp"

#line 5 "src/utility/bit/popcount.hpp"

#include <cassert>

namespace luz {

  usize popcount(u64 x) {
    assert(__cplusplus <= 201703L);

#ifdef __GNUC__
    return __builtin_popcountll(x);
#endif

    x -= (x >> 1) & 0x5555555555555555;
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f;
    return x * 0x0101010101010101 >> 56 & 0x7f;
  }

} // namespace luz
#line 6 "src/utility/bit/bit-width.hpp"

#line 8 "src/utility/bit/bit-width.hpp"

namespace luz {

  usize bit_width(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 0;
    }

#ifdef __GNUC__
    return 64 - __builtin_clzll(x);
#endif

    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return popcount(x);
  }

} // namespace luz
#line 2 "src/utility/bit/count-trailing-0s.hpp"

#line 6 "src/utility/bit/count-trailing-0s.hpp"

#line 8 "src/utility/bit/count-trailing-0s.hpp"

namespace luz {

  usize countr_zero(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 64;
    }

#ifdef __GNUC__
    return __builtin_ctzll(x);
#endif

    return popcount((x & -x) - 1);
  }

} // namespace luz
#line 7 "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"

#line 9 "src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp"
#include <vector>

namespace luz {

  template < class operator_structure >
  class RangeMappingPointFoldSegmentTree {
    using O  = operator_structure;
    using OT = typename O::value_type;

    std::vector< OT > tree;

    void evaluate_lazy(OT &x, const OT &y) {
      x = O::operation(x, y);
    }

    void propagate(const usize index) {
      evaluate_lazy(tree[index << 1 | 0], tree[index]);
      evaluate_lazy(tree[index << 1 | 1], tree[index]);
      tree[index] = O::identity();
    }

    void propagate_bound(const usize index) {
      if (index == 0) return;

      const usize l = countr_zero(index) + 1;
      const usize r = bit_width(index);
      for (usize i: rrep(l, r)) {
        propagate(index >> i);
      }
    }

   public:
    using value_type = OT;

    RangeMappingPointFoldSegmentTree() = default;

    explicit RangeMappingPointFoldSegmentTree(const usize n)
        : tree(n * 2, O::identity()) {}

    explicit RangeMappingPointFoldSegmentTree(const usize n, OT v)
        : RangeMappingPointFoldSegmentTree(n) {
      build(std::vector< OT >(n, v));
    }

    explicit RangeMappingPointFoldSegmentTree(
        const std::vector< OT > &vs)
        : RangeMappingPointFoldSegmentTree(vs.size()) {
      build(vs);
    }

    void build(const std::vector< OT > &vs) {
      for (usize i: rep(0, vs.size())) {
        tree[i + size()] = vs[i];
      }
    }

    usize size() const {
      return tree.size() / 2;
    }

    void set(usize index, const OT x) {
      assert(index < size());
      index += size();

      const usize l = 1;
      const usize r = bit_width(index);
      for (usize i: rrep(l, r)) {
        propagate(index >> i);
      }

      tree[index] = x;
    }

    void apply(usize index, const OT &x) {
      return apply(index, index + 1, x);
    }

    void apply(usize first, usize last, const OT &x) {
      assert(first <= last);
      assert(last <= size());

      first += size();
      last += size();

      propagate_bound(first);
      propagate_bound(last);

      while (first != last) {
        if (first & 1) {
          evaluate_lazy(tree[first], x);
          first += 1;
        }
        first >>= 1;

        if (last & 1) {
          last -= 1;
          evaluate_lazy(tree[last], x);
        }
        last >>= 1;
      }
    }

    OT fold(usize index) {
      assert(index < size());

      index += size();

      OT result = tree[index];
      while (index != 1) {
        index >>= 1;
        evaluate_lazy(result, tree[index]);
      }
      return result;
    }
  };

  template < class operator_structure >
  using DualSegmentTree =
      RangeMappingPointFoldSegmentTree< operator_structure >;

} // namespace luz
#line 5 "src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp"

namespace luz {

  template < typename T >
  using RangeChminQuerySolver =
      DualSegmentTree< monoid::RangeChminQueryMonoid< T > >;

} // namespace luz

区間 chmin クエリ solver (Range ChangeMin Query Solver) (src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp)

コンストラクタ

Depends on

Verified with

Code

区間 chmin クエリ solver (Range ChangeMin Query Solver)
(src/data-structure/segment-tree/presets/range-chmin-query-solver.hpp)