src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Include: #include "src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp"

Depends on

Required by

区間更新 + 区間和クエリ solver (Range Update Range Sum Query Solver) (src/data-structure/segment-tree/presets/range-update-range-sum-query-solver.hpp)

Verified with

test/aoj/dsl_2_i.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"
#include "src/data-structure/segment-tree/presets/monoid/operator-structure-update.hpp"
#include "src/data-structure/segment-tree/presets/monoid/value-structure-sum.hpp"

namespace luz::monoid {

  template < typename T, T ID >
  class RangeUpdateRangeSumQueryMonoid {

    class node_type {
      using F = node_type;

     public:
      T value;
      usize count;

      node_type(): value(), count() {}
      node_type(T v, usize c): value(v), count(c) {}

      F operator+(const F &b) {
        return F(value + b.value, count + b.count);
      }
    };

    using V  = RangeSumQueryMonoid< node_type >;
    using VT = typename V::value_type;
    using O  = RangeUpdateQueryMonoid< T, ID >;
    using OT = typename O::value_type;

   public:
    using value_structure    = V;
    using operator_structure = O;

    static constexpr VT operation(VT a, OT b) {
      return b == ID ? a : VT(b * a.count, a.count);
    }
  };

} // namespace luz::monoid

#line 2 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.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 2 "src/data-structure/segment-tree/presets/monoid/operator-structure-update.hpp"

namespace luz::monoid {

  template < typename T, T ID >
  class RangeUpdateQueryMonoid {

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return b == ID ? a : b;
    }

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

} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/presets/monoid/value-structure-sum.hpp"

namespace luz::monoid {

  template < typename T >
  class RangeSumQueryMonoid {

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return a + b;
    }

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

} // namespace luz::monoid
#line 6 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-sum.hpp"

namespace luz::monoid {

  template < typename T, T ID >
  class RangeUpdateRangeSumQueryMonoid {

    class node_type {
      using F = node_type;

     public:
      T value;
      usize count;

      node_type(): value(), count() {}
      node_type(T v, usize c): value(v), count(c) {}

      F operator+(const F &b) {
        return F(value + b.value, count + b.count);
      }
    };

    using V  = RangeSumQueryMonoid< node_type >;
    using VT = typename V::value_type;
    using O  = RangeUpdateQueryMonoid< T, ID >;
    using OT = typename O::value_type;

   public:
    using value_structure    = V;
    using operator_structure = O;

    static constexpr VT operation(VT a, OT b) {
      return b == ID ? a : VT(b * a.count, a.count);
    }
  };

} // namespace luz::monoid