MonoidRangeFoldEulerTourSumRangeOperateAdd - fold:区間オイラーツアー和, operate:区間加算
(lib/99-operator/monoid-lazy/MonoidRangeFoldEulerTourSumRangeOperateAdd.cpp)

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

Verified with

• test/graph/Tree-eulertour.test.cpp

Code

/*
 * @title MonoidRangeFoldEulerTourSumRangeOperateAdd - fold:区間オイラーツアー和, operate:区間加算
 * @docs md/operator/monoid-lazy/MonoidRangeEulerTourSumRangeAdd.md
 */
template<class T, class U> struct MonoidRangeFoldEulerTourSumRangeOperateAdd {
	using TypeNode = T;
	using TypeLazy = U;
	inline static constexpr TypeNode unit_node = {0,0};
	inline static constexpr TypeLazy unit_lazy = 0;
	inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return {l.first+r.first,l.second+r.second};}
	inline static constexpr TypeLazy func_lazy(TypeLazy old_lazy,TypeLazy new_lazy){return old_lazy+new_lazy;}
	inline static constexpr TypeNode func_operate(TypeNode node,TypeLazy lazy,int l, int r){return {node.first+node.second*lazy,node.second};}
	inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;}
	// LazySegmentTree<NodeSumRangeUpdate<ll,ll>> Seg(N,0);
};

#line 1 "lib/99-operator/monoid-lazy/MonoidRangeFoldEulerTourSumRangeOperateAdd.cpp"
/*
 * @title MonoidRangeFoldEulerTourSumRangeOperateAdd - fold:区間オイラーツアー和, operate:区間加算
 * @docs md/operator/monoid-lazy/MonoidRangeEulerTourSumRangeAdd.md
 */
template<class T, class U> struct MonoidRangeFoldEulerTourSumRangeOperateAdd {
	using TypeNode = T;
	using TypeLazy = U;
	inline static constexpr TypeNode unit_node = {0,0};
	inline static constexpr TypeLazy unit_lazy = 0;
	inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return {l.first+r.first,l.second+r.second};}
	inline static constexpr TypeLazy func_lazy(TypeLazy old_lazy,TypeLazy new_lazy){return old_lazy+new_lazy;}
	inline static constexpr TypeNode func_operate(TypeNode node,TypeLazy lazy,int l, int r){return {node.first+node.second*lazy,node.second};}
	inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;}
	// LazySegmentTree<NodeSumRangeUpdate<ll,ll>> Seg(N,0);
};

Back to top page