ある一つの区間に対してたこ焼きの追加クエリと皿の反転クエリがそれぞれ \(0\) 個以上任意の順番で行われたとき、どのような操作が行われたことになるかを考えます。

最後の反転クエリ以前に行われた追加クエリの影響はなくなるため、これは \(0\) 回以上の反転クエリののち、\(1\) 回の追加クエリが行われたことに言い換えることができます。 よって、複数回の更新クエリは非負整数の \(2\) つ組 \((a,b)\) を用いて、\(a\) 回の反転クエリののち \(b\) 個のたこ焼きを追加する操作として表現することができます。 このような操作を単に \((a,b)\) と書くことにし、\((a,b)\) のあとに \((c,d)\) を行うことを \((a,b)\oplus(c,d)\) と書くことにすると、\[(a,b)\oplus(c,d)=\begin{cases}(a,b+d)&\quad(c=0)\\ (a+c,d)&\quad(c\neq0)\end{cases}\]となります。

次に、列に対してどのような情報を持てば、任意の非負整数の \(2\) つ組 \((a,b)\) に対して操作 \((a,b)\) が行われたあとの列に対する最大値が得られるかを考えます。 例えば \(\bigl(\)現在の列の最大値\({},{}\) 現在いくつの皿が表向きになっているか\({},{}\) 現在いくつの皿が裏向きになっているか\(\bigr)\) のような \(3\) つ組を持つと、この \(3\) つ組の値が \((x,y,z)\) であるような列に対して操作 \((a,b)\) を行ったあとの列に対する値は \[\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}\] となります。

これらは、遅延伝播セグメント木や遅延評価セグメント木などと呼ばれるデータ構造を使って管理することができる条件を満たします。 よって、この問題を \(O(N+Q\log N)\) 時間で解くことができました。

実装例は以下のようになります。

#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;
}