[nilknarf]

Although I didn't know it by that name, I have seen the bicyclic semigroup in competitive programming many times before (usually any problem involving intervals/brackets and segment trees).

For example in this problem https://codeforces.com/contest/1285/problem/E, one solution is to parse and count the number of top-level parentheses after small modifications. For example the original string might be "(()())()". Then "(()())" is 1, "(())()" is 2, "()()()" is 3.

This is solved with the following monoid to make incremental reparsing fast:

    neutral = Node(0, 0, 0)


    def combine(x, y):
        # Each node tracks numClose, numCount, numOpen:
        # e.g., )))) (...)(...)(...) ((((((
        if x.open == y.close == 0:
            ret = x.close, x.count + y.count, y.open
        elif x.open == y.close:
            ret = x.close, x.count + 1 + y.count, y.open
        elif x.open > y.close:
            ret = x.close, x.count, x.open - y.close + y.open
        elif x.open < y.close:
            ret = x.close + y.close - x.open, y.count, y.open
        return Node(*ret)

Reference solution: https://codeforces.com/contest/1285/submission/92169958

Monoid cached trees are extremely popular in competitive programming, but never by that name. It's always referred to as a "segment tree" without using any mathematical terminology more advanced than "associativity".

Due to its popularity, all kinds of crazy monoid states have already been explored (though you need to squint a bit to see them due to the terminology mismatch): https://codeforces.com/blog/entry/15890. I've never seen stack used though. You almost always want to compress the state as much as possible and the problems I've seen only needed stack depth (aka the bicyclic semigroup), not contents. Requiring O(N) to merge also highly limits its use cases.

Anyway, not sure how relevant this is to you since the use of monoids in data structures and for parallelism is slightly different (binary merges all the way down versus stopping at some chunk size).