The first thing that I see is that you're using Strings for input. Haskell Strings are linked lists of Unicode characters and are unsuitable for processing large amount of data. You should use lazy Bytestrings instead.

The second thing that is immediately evident is memory usage. Your program takes 200 megabytes on a test case with n < 10⁴. That's due to excessive laziness: during program execution unevaluated thunks are accumulated and eat up all the memory. (Look here for a simple example.) The solution if to throw in some strictness annotations and introduce strict fields into your SegmentTree data type. And while we're at it, let's add GHC option -funbox-strict-fields, which basically replaces Ints (that are equivalent of java.lang.Integer) with Int#s (that are raw machine integers). (Warning: in general, you need to be careful with these two optimizations: they aren't default for a reason and can make performance worse.)

We get the following code: 4060212. (Apologies for Codeforces' messed up syntax highlighting.) It's now using only 2 megabytes of memory, which is good, but it still fails the same test case. There's definitely something very wrong here, so it seems that it's time to actually read problem statement and the code :)

You're implementing a segment tree with updates on sub-segments. For this to be efficient, updates to children nodes must be postponed until they are actually needed. Consider, for example, two consecutive updates of the same node: first with the value 1, then with the value 2. You want only the second update to be propagated to children. You may think that due to Haskell's laziness it's done automatically, but it's not… In the first update children of the node are replaced with thunks. In the second update they are replaced with new thunks, but they must reference old ones. When you actually need the value of a child, you'll have to unpack the whole Russian nested doll of thunks. So updates to children are postponed but not accumulated. Maybe it's possible to employ Haskell's laziness, but I don't know how.

We need the same implementation as in an imperative program: add a new field to your SegmentTree node, that will hold the value that this node has been updated with, but not yet propagated to its children. Because you're storing the maximum on sub-segment, the value itself doesn't need to be stored (it's equal to the sub-segment maximum), so we need only Bool flag that will be set to True if there is an unpropagated update waiting at this node. Here is the new version that passes system tests: 4065385. Note two things: 1. children are updated only in one case for update function; 2. query got a new case for when the flag is True (then the whole sub-segment contains only one value, and there's no need to descend to children). I also took the liberty of removing l and r fields from your SegmentTree node: they never change and we can compute them on the fly. In an imperative program it doesn't matter, but in a functional one new nodes are created all the time, so constant fields introduce unnecessary copying.

Finally, I'm a Haskell beginner as well, so take everything I said with a grain of salt :)

Here is my solution written on Haskell without Segment Tree http://codeforces.net/contest/273/submission/4086244. In any case, could you please describe what do you mean by "advantage of Haskell"? If you mean cool type system, laziness or declarative programming, all solutions mentioned above use it. Of course, they don't use features like functional dependencies and meta-programming, but it's okay, because a common and in general fruitful way is to go from solution to language, not in backward direction.

Hey there,

I came across your post while searching for "haskell segment tree" (I'm pretty sure many others do too and hope this helps). I also feel unsatisfied with the explicitly lazy version of segment tree by slycelote. After many tries I've finally found the space leak in your submissions (and my previous submissions). In the lazy propagation case of update, we don't really need the left and right children. What we are trying to do here is to build a new sub-tree which resembles the current sub-tree, but with all values set to x (the updating value). As the shape of a sub-tree is fully determined by the segment covered by its root, we can ignore the left and right children and lazily build the new sub-tree using just the segment. However, flag is not totally useless here: we can still employ it to break early in the query function: if flag is True, all nodes in the current sub-tree have the same value and we don't have to dig deeper.

Here's the submission that doesn't use flag (it's there but always False): http://codeforces.net/contest/273/submission/29282195

And here's the version that use flag (see the make function): http://codeforces.net/contest/273/submission/29282263