sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include <bits/stdc++.h> using namespace std; // monoids struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; struct MinMonoid { using T = int; static T id() { return (1u << 31) - 1; } static T op(T a, T b) { return min(a, b); } }; struct MaxMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return max(a, b); } }; struct AddRangeMonoid { using T = pair<int, int>; static T id() { return {0, 0}; } static T op(T a, T b) { return {a.first + b.first, a.second + b.second}; } }; struct UpdateMonoid { using T = int; static T id() { return -1; } static T op(T a, T b) { return b == id() ? a : b; } }; struct AffineMonoid { using T = pair<int, int>; static T id() { return {1, 0}; } static T op(T a, T b) { return {a.first * b.first, a.second * b.first + b.second}; } }; struct CountMinMonoid { using T = pair<int, int>; // min, count static T id() { return {(1u << 31) - 1, 0}; } static T op(T a, T b) { if (a.first < b.first) return a; if (a.first > b.first) return b; return {a.first, a.second + b.second}; } }; // actions MaxMonoid::T act(MaxMonoid::T a, AddMonoid::T b) { return a + b; } AddRangeMonoid::T act(AddRangeMonoid::T a, AffineMonoid::T b) { return {a.first * b.first + a.second * b.second, a.second}; } AddRangeMonoid::T act(AddRangeMonoid::T a, AddMonoid::T b) { return {a.first + a.second * b, a.second}; } AddRangeMonoid::T act(AddRangeMonoid::T a, UpdateMonoid::T b) { if (b == UpdateMonoid::id()) return a; return {b * a.second, a.second}; }
#line 1 "misc/monoids.cpp" #include <bits/stdc++.h> using namespace std; // monoids struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; struct MinMonoid { using T = int; static T id() { return (1u << 31) - 1; } static T op(T a, T b) { return min(a, b); } }; struct MaxMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return max(a, b); } }; struct AddRangeMonoid { using T = pair<int, int>; static T id() { return {0, 0}; } static T op(T a, T b) { return {a.first + b.first, a.second + b.second}; } }; struct UpdateMonoid { using T = int; static T id() { return -1; } static T op(T a, T b) { return b == id() ? a : b; } }; struct AffineMonoid { using T = pair<int, int>; static T id() { return {1, 0}; } static T op(T a, T b) { return {a.first * b.first, a.second * b.first + b.second}; } }; struct CountMinMonoid { using T = pair<int, int>; // min, count static T id() { return {(1u << 31) - 1, 0}; } static T op(T a, T b) { if (a.first < b.first) return a; if (a.first > b.first) return b; return {a.first, a.second + b.second}; } }; // actions MaxMonoid::T act(MaxMonoid::T a, AddMonoid::T b) { return a + b; } AddRangeMonoid::T act(AddRangeMonoid::T a, AffineMonoid::T b) { return {a.first * b.first + a.second * b.second, a.second}; } AddRangeMonoid::T act(AddRangeMonoid::T a, AddMonoid::T b) { return {a.first + a.second * b, a.second}; } AddRangeMonoid::T act(AddRangeMonoid::T a, UpdateMonoid::T b) { if (b == UpdateMonoid::id()) return a; return {b * a.second, a.second}; }