AOJ-「RMQ and RAQ」 遅延セグ木でminを求めるときにモノイドの初期化を0にしてはいけない理由

言いたいこと

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_H&lang=ja
この問題を解いていて、遅延セグ木の実装をしていたときに解説記事とほぼ同じコードなのになぜか自分の出力はWAでした。その原因を探ってみるとモノイドの初期化を0にしていたことが原因で、正しくはINFでした。
「prodなどで答えを求めるとき、モノイドの初期化の値がprodなどで答えを求めていく前の初期化の値となるので、minを求めるときに0を初期値としておくとWAになってしまう。なのでモノイドの初期値はINFにして、サイズn初期値0の配列を遅延セグ木の初期化に使う」

原因を調べてみた

私が書いたコードと正しいコードを張ります。ACLの遅延セグ木を使う用のコードを書きます(AOJなので実際に使うことはできません、ACLが一番知られている書き方だと思うので使います)

私が書いた間違いのコード

using S=int;
int op(int a, int b) {return min(a, b);}
int e() { return 0; }
using F=int;
int mapping(int a, int b) {return a+b;}
int composition(int a, int b) {retrum a+b;}
int id() { return 0; }

int main(){//入力は省略します
  lazy_segtree<S,op,e,ll,mapping,composition,id> seg(n);
}

このようなコードを私は書いていました。しかしこれでは問題のリンク先にあるサンプル1の3つ目のクエリがWAになってしまいます。なぜだろうと解説記事にあるコードを見比べてみると違ってる部分がありました。以下は解説記事のコードをACL版にしたコードです。

正しいコード

using S=int;
int op(int a, int b) {return min(a, b);}
int e() { return INF; }
using F=int;
int mapping(int a, int b) {return a+b;}
int composition(int a, int b) {retrum a+b;}
int id() { return 0; }

int main(){//入力は省略します
  vector<int>a(n,0);
  lazy_segtree<S,op,e,ll,mapping,composition,id> seg(a);
}

さて、2つのコードで変わった内容が2つあります。1つ目は関数eの単位元が0からINFになったこと。2つ目は遅延セグ木のサイズを決めるときにvectorを引数にしていて、サイズnで中身が0で初期化された配列です。つまり何が違うのか？というと「モノイドの初期化の値」が変わりました。問題文にはaiは全て0で初期化されている、とあるので私はモノイドの初期化を0にしていましたがそれが間違いでした。
ではなぜモノイドの初期化を0にすると間違いになるのでしょうか？ここで私が参考にしたけんちょんさんの解説記事のコードを見てみます(おそらくACLとやっている内容は同じだと思います)、遅延セグ木のコードは長いので説明に使いたい部分だけ貼ります。

prodのコード

 Monoid prod(int l, int r) {
        assert(0 <= l && l <= r && r <= N);
        if (l == r) return IDENTITY_MONOID;
        l += offset, r += offset;
        for (int h = log; h >= 1; --h) {
            if (((l >> h) << h) != l) push_lazy(l >> h);
            if (((r >> h) << h) != r) push_lazy(r >> h);
        }
        // ↓ 9行目
        Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) val_left = OP(val_left, dat[l++]);
            if (r & 1) val_right = OP(dat[--r], val_right);
        }
        return OP(val_left, val_right);
    }

まず、「IDENTITY_MONOID」という変数は、初期化の際に渡したモノイドの初期化、つまり関数eでreturnした値のことです。そして9行目のコードを見るとval_leftとval_rightという変数を用意して、それの値をモノイドの初期化の値と同じにしています。さらにその下のコードを見ると、セグ木の仕組みを知っているならばわかると思いますが、セグ木内を再帰関数で掘っていって、求まった値でOPという関数に渡して、その結果をval_leftとval_rightに更新しています、OPというのは、遅延セグ木の初期化で設定した関数opのことで、つまり今回の問題の場合はminを返す関数となります。としたとき、「モノイドの初期化の値がminに使われる」と気づくことができます。そうしたとき、私の間違いだったコードのように初期化を0としてしまうと、0とminを取ることになるので、0より大きい値が答えのときは0とminを取って、0が返ってくるのでWAになるというわけです。
結論としては「prodなどで答えを求めるとき、モノイドの初期化の値がprodなどで答えを求めていく前の初期化の値となるので、minを求めるときに0を初期値としておくとWAになってしまう。なのでモノイドの初期値はINFにして、サイズn初期値0の配列を遅延セグ木の初期化に使う」ということになります。

参考にしたサイト