MonoidRangeFoldSumRangeOperateAffine - fold:区間和, operate:区間アフィン変換
(lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAffine.cpp)

• View this file on GitHub
• Last update: 2023-06-03 10:08:48+09:00

Verified with

• test/binary-search-tree/LazyRandomizedBinarySearchTreeSequence-reverse.test.cpp
• test/binary-search-tree/LazyRandomizedBinarySearchTreeSequence-rsqrafq.test.cpp
• test/binary-search-tree/LazySplayTreeSequence-reverse.test.cpp
• test/binary-search-tree/LazySplayTreeSequence-rsqrafq.test.cpp
• test/segment-tree/DualSegmentTree-pcq.test.cpp

Code

/*
 * @title MonoidRangeFoldSumRangeOperateAffine - fold:区間和, operate:区間アフィン変換
 * @docs md/operator/monoid-lazy/MonoidRangeSumRangeAffine.md
 */
template<class T, class U> struct MonoidRangeFoldSumRangeOperateAffine {
	using TypeNode = T;
	using TypeLazy = U;
	inline static constexpr TypeNode unit_node = 0;
	inline static constexpr TypeLazy unit_lazy = {1,0};
	inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
	inline static constexpr TypeLazy func_lazy(TypeLazy old_lazy,TypeLazy new_lazy){return {new_lazy.first*old_lazy.first,new_lazy.first*old_lazy.second+new_lazy.second};}
	inline static constexpr TypeNode func_operate(TypeNode node,TypeLazy lazy,int l, int r){return {node*lazy.first+lazy.second*(r-l)};}
	inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;}
};

#line 1 "lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAffine.cpp"
/*
 * @title MonoidRangeFoldSumRangeOperateAffine - fold:区間和, operate:区間アフィン変換
 * @docs md/operator/monoid-lazy/MonoidRangeSumRangeAffine.md
 */
template<class T, class U> struct MonoidRangeFoldSumRangeOperateAffine {
	using TypeNode = T;
	using TypeLazy = U;
	inline static constexpr TypeNode unit_node = 0;
	inline static constexpr TypeLazy unit_lazy = {1,0};
	inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
	inline static constexpr TypeLazy func_lazy(TypeLazy old_lazy,TypeLazy new_lazy){return {new_lazy.first*old_lazy.first,new_lazy.first*old_lazy.second+new_lazy.second};}
	inline static constexpr TypeNode func_operate(TypeNode node,TypeLazy lazy,int l, int r){return {node*lazy.first+lazy.second*(r-l)};}
	inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;}
};

Back to top page