(1) RangeUpdateRangeMaximumQuerySolver< T, ID >(usize n)
(2) RangeUpdateRangeMaximumQuerySolver< T, ID >(usize n, T v)
(3) RangeUpdateRangeMaximumQuerySolver< T, ID >(std::vector< T > vs)
#line 2 "src/data-structure/segment-tree/presets/range-update-range-maximum-query-solver.hpp"
#line 2 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-maximum.hpp"
#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-maximum.hpp"
#include <algorithm>
#include <limits>
namespace luz :: monoid {
template < typename T >
class RangeMaximumQueryMonoid {
static constexpr T identity_ { std :: numeric_limits < T >:: min ()};
public:
using value_type = T ;
static constexpr T operation ( T a , T b ) {
return std :: max ( a , b );
}
static constexpr T identity () {
return identity_ ;
}
};
} // namespace luz::monoid
#line 5 "src/data-structure/segment-tree/presets/monoid/combined-structure-update-maximum.hpp"
namespace luz :: monoid {
template < typename T , T ID >
class RangeUpdateRangeMaximumQueryMonoid {
using V = RangeMaximumQueryMonoid < T > ;
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 T operation ( VT a , OT b ) {
return b == ID ? a : b ;
}
};
} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/range-mapping-range-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-range-fold-segment-tree.hpp"
#line 9 "src/data-structure/segment-tree/range-mapping-range-fold-segment-tree.hpp"
#include <vector>
namespace luz {
template < class combined_structure >
class RangeMappingRangeFoldSegmentTree {
using C = combined_structure ;
using V = typename C :: value_structure ;
using VT = typename V :: value_type ;
using O = typename C :: operator_structure ;
using OT = typename O :: value_type ;
class node_type {
public:
VT value ;
OT lazy ;
node_type ( const VT value_ , const OT lazy_ )
: value ( value_ ),
lazy ( lazy_ ) {}
VT get () {
return C :: operation ( value , lazy );
}
};
std :: vector < node_type > tree ;
void evaluate_lazy ( OT & x , const OT & y ) {
x = O :: operation ( x , y );
}
void recalc ( usize index ) {
tree [ index ]. value = V :: operation ( tree [ index << 1 | 0 ]. get (),
tree [ index << 1 | 1 ]. get ());
}
void recalc_bound ( usize index ) {
if ( index == 0 ) return ;
const usize l = countr_zero ( index ) + 1 ;
const usize r = bit_width ( index );
for ( usize i : rep ( l , r )) {
recalc ( index >> i );
}
}
void propagate ( const usize index ) {
evaluate_lazy ( tree [ index << 1 | 0 ]. lazy , tree [ index ]. lazy );
evaluate_lazy ( tree [ index << 1 | 1 ]. lazy , tree [ index ]. lazy );
tree [ index ]. lazy = 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 = VT ;
RangeMappingRangeFoldSegmentTree () = default ;
explicit RangeMappingRangeFoldSegmentTree ( const usize n )
: tree ( n * 2 , node_type ( V :: identity (), O :: identity ())) {}
explicit RangeMappingRangeFoldSegmentTree ( const usize n ,
const VT v )
: RangeMappingRangeFoldSegmentTree ( n ) {
build ( std :: vector < VT > ( n , v ));
}
explicit RangeMappingRangeFoldSegmentTree (
const std :: vector < VT > & vs )
: RangeMappingRangeFoldSegmentTree ( vs . size ()) {
build ( vs );
}
void build ( const std :: vector < VT > & vs ) {
usize n = vs . size ();
assert ( 2 * n == tree . size ());
for ( usize i : rep ( 0 , n )) {
tree [ i + n ] = node_type ( vs [ i ], O :: identity ());
}
for ( usize index : rrep ( 1 , n )) {
recalc ( index );
}
}
usize size () const {
return tree . size () / 2 ;
}
void set ( usize index , const VT 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 ] = node_type ( x , O :: identity ());
for ( usize i : rep ( l , r )) {
recalc ( index >> i );
}
}
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 );
const usize c_first = first ;
const usize c_last = last ;
while ( first != last ) {
if ( first & 1 ) {
evaluate_lazy ( tree [ first ]. lazy , x );
first += 1 ;
}
first >>= 1 ;
if ( last & 1 ) {
last -= 1 ;
evaluate_lazy ( tree [ last ]. lazy , x );
}
last >>= 1 ;
}
recalc_bound ( c_first );
recalc_bound ( c_last );
}
VT fold ( usize index ) {
return fold ( index , index + 1 );
}
VT fold ( usize first , usize last ) {
assert ( first <= last );
assert ( last <= size ());
first += size ();
last += size ();
propagate_bound ( first );
recalc_bound ( first );
propagate_bound ( last );
recalc_bound ( last );
VT fold_l = V :: identity ();
VT fold_r = V :: identity ();
while ( first != last ) {
if ( first & 1 ) {
fold_l = V :: operation ( fold_l , tree [ first ]. get ());
first += 1 ;
}
first >>= 1 ;
if ( last & 1 ) {
last -= 1 ;
fold_r = V :: operation ( tree [ last ]. get (), fold_r );
}
last >>= 1 ;
}
return V :: operation ( fold_l , fold_r );
}
VT fold_all () {
return ( size () ? tree [ 1 ]. get () : V :: identity ());
}
};
template < class combined_structure >
using LazySegmentTree =
RangeMappingRangeFoldSegmentTree < combined_structure > ;
} // namespace luz
#line 5 "src/data-structure/segment-tree/presets/range-update-range-maximum-query-solver.hpp"
namespace luz {
template < typename T , T ID >
using RangeUpdateRangeMaximumQuerySolver = LazySegmentTree <
monoid :: RangeUpdateRangeMaximumQueryMonoid < T , ID > > ;
} // namespace luz