algebra/monoid_s_f/monoid_max01_flip.hpp

• View this file on GitHub
• Last update: 2024-03-24 19:02:42+09:00
• Include: #include "algebra/monoid_s_f/monoid_max01_flip.hpp"
• Link: https://atcoder.jp/contests/abc322/tasks/abc322_f

Depends on

• algebra/monoid_f/monoid_flip.hpp

Code

#pragma once

// https://atcoder.jp/contests/abc322/tasks/abc322_f
// MS
template <class T> struct MonoidMax01 {
    using S = std::array<T, 7>;  // {max0, left0, right0, max1, left1, right1, length}
    static constexpr S op(S a, S b) {
        S res;
        for (int i = 0; i < 6; i += 3) {
            res[i + 0] = std::max({a[i + 0], b[i + 0], a[i + 2] + b[i + 1]});
            res[i + 1] = a[6] == a[i + 1] ? a[i + 1] + b[i + 1] : a[i + 1];
            res[i + 2] = b[6] == b[i + 2] ? a[i + 2] + b[i + 2] : b[i + 2];
        }
        res[6] = a[6] + b[6];
        return res;
    }
    static constexpr S e() { return {0, 0, 0, 0, 0, 0, 0}; }
    static constexpr S e0() { return {1, 1, 1, 0, 0, 0, 1}; }
    static constexpr S e1() { return {0, 0, 0, 1, 1, 1, 1}; }
};
#include "algebra/monoid_f/monoid_flip.hpp"
// MSF
template <class T> struct MonoidMax01Flip {
    using MS = MonoidMax01<T>;
    using MF = MonoidFlip;
    using S = typename MS::S;
    using F = typename MF::F;
    static constexpr S mapping(F f, S x) {
        if (!f) return x;
        for (int i = 0; i < 3; i++) std::swap(x[i], x[i + 3]);
        return x;
    }
};

#line 2 "algebra/monoid_s_f/monoid_max01_flip.hpp"

// https://atcoder.jp/contests/abc322/tasks/abc322_f
// MS
template <class T> struct MonoidMax01 {
    using S = std::array<T, 7>;  // {max0, left0, right0, max1, left1, right1, length}
    static constexpr S op(S a, S b) {
        S res;
        for (int i = 0; i < 6; i += 3) {
            res[i + 0] = std::max({a[i + 0], b[i + 0], a[i + 2] + b[i + 1]});
            res[i + 1] = a[6] == a[i + 1] ? a[i + 1] + b[i + 1] : a[i + 1];
            res[i + 2] = b[6] == b[i + 2] ? a[i + 2] + b[i + 2] : b[i + 2];
        }
        res[6] = a[6] + b[6];
        return res;
    }
    static constexpr S e() { return {0, 0, 0, 0, 0, 0, 0}; }
    static constexpr S e0() { return {1, 1, 1, 0, 0, 0, 1}; }
    static constexpr S e1() { return {0, 0, 0, 1, 1, 1, 1}; }
};
#line 2 "algebra/monoid_f/monoid_flip.hpp"

// MF
struct MonoidFlip {
    using F = int;
    static constexpr F composition(F f, F g) { return f ^ g; }
    static constexpr F id() { return 0; }
};
#line 22 "algebra/monoid_s_f/monoid_max01_flip.hpp"
// MSF
template <class T> struct MonoidMax01Flip {
    using MS = MonoidMax01<T>;
    using MF = MonoidFlip;
    using S = typename MS::S;
    using F = typename MF::F;
    static constexpr S mapping(F f, S x) {
        if (!f) return x;
        for (int i = 0; i < 3; i++) std::swap(x[i], x[i + 3]);
        return x;
    }
};

Back to top page