For a fixed segment, what happens when zero or more addition queries and flip queries were performed in any order?

Any addition queries performed before the last flip query have no effect, so any operation sequence can be regarded as a sequence of zero or more flip queries and one addition query. Thus, multiple update queries can be represented as a pair of non-negative integers \((a,b)\), meaning that \(a\) flip queries and \(b\) addition queries have been performed in this order. When we simply denote these operations by \((a,b)\), and performing \((a,b)\) after \((c,d)\) by \((a,b)\oplus(c,d)\), we have \[(a,b)\oplus(c,d)=\begin{cases}(a,b+d)&\quad(c=0)\\ (a+c,d)&\quad(c\neq0).\end{cases}\]

Next, consider what kind of information we need to maintain so that we can obtain the maximum value for the segment after operation \((a,b)\) was applied, for any pair of non-negative integers \((a,b)\). For example, we can think of storing a triple \(\bigl(\)the maximum value\({},{}\) the number of face-up plates\({},{}\) the number of face-down plates\(\bigr)\) within the current segment. When a segment with this triplet \((x,y,z)\) undergoes an operation \((a,b)\), this triple becomes\[\begin{cases}(0,y,z)&(a\equiv0\pmod2\wedge y=0)\\ (x+b,y,z)&(a=0\wedge y\neq0)\\ (b,y,z)&(a\gt0\wedge a\equiv0\pmod2\wedge y\neq0)\\ (0,z,y)&(a\equiv1\pmod2\wedge z=0)\\ (b,z,y)&(a\equiv1\pmod2\wedge z\neq0).\end{cases}\]

This structure is applicable as a structure that can be managed in a data structure widely known as a lazy-propagation segment tree or lazy-evaluation segment tree. Therefore, the problem has been solved in \(O(N+Q\log N)\) time.

The following is sample code.

#include <iostream>
#include <vector>
#include <atcoder/lazysegtree>

int main() {
    using namespace std;

    unsigned N, Q;
    cin >> N >> Q;

    struct value { unsigned long max; unsigned up, down; };
    struct op { unsigned flip; unsigned long add; };
    atcoder::lazy_segtree<value,
                          [](const value lhs, const value rhs) { return value{max(lhs.max, rhs.max), lhs.up + rhs.up, lhs.down + rhs.down}; },
                          [] { return value{}; },
                          op,
                          [](const op operation, const value segment) {
                              return value{
                                  (operation.flip & 1 ? segment.down : segment.up) ? operation.flip ? operation.add : segment.max + operation.add : 0,
                                  operation.flip & 1 ? segment.down : segment.up,
                                  operation.flip & 1 ? segment.up : segment.down
                              };
                          },
                          [](const op lhs, const op rhs) { return op{lhs.flip + rhs.flip, (lhs.flip ? 0 : rhs.add) + lhs.add}; },
                          [] { return op{}; }> segment_tree(vector(N, value{0, 1, 0}));

    for (unsigned q{}; q < Q; ++q) {
        unsigned t;
        cin >> t;
        if (t == 1) {
            unsigned L, R, X;
            cin >> L >> R >> X;
            segment_tree.apply(L - 1, R, op{0, X});
        } else if (t == 2) {
            unsigned L, R;
            cin >> L >> R;
            segment_tree.apply(L - 1, R, op{1, 0});
        } else {
            unsigned L, R;
            cin >> L >> R;
            cout << segment_tree.prod(L - 1, R).max << endl;
        }
    }
    return 0;
}