USACO HOL09 Problem 'holpaint' Analysis

by Anton Anastasov

This problem can be solved using a segment tree data structure. Let's simplify the problem by allowing the picture to be only one column in width. We need to be able to perform two kind of operations over this data structure:

• paint(a, b, {0, 1}) - paints the interval of rows [a, b) (from a to b, excluding b) with zeros or ones
• count() - counts the number of correctly colored cells according to the picture (for the whole row)

Let's suppose each node has children left(node) and right(node), and each node is responsible for [from(node), to(node)) (excluding the right bound). This operations can be implemented in O(log R) and O(1) using segment tree. Let's see what information should be kept in every node of the tree:

• the number of cells that are correctly colored in [from(node), to(node)) (1)
• the color of the node {0 - if the whole interval is of zeros, 1 - only ones, 2 - only zeros, only ones or mixed}

colorOf(node) and correct(node) denotes these two fields.

It may seem that only the first field is enough, but what happens when we perform the operation paint(0, R, 1) (paint the whole column with ones)? We should first update the information in the root of the tree, after that recursively update the information in both the left and the right subtrees. This process will update the whole tree and will be O(R), rather than O(log R). That's why we use the second field. When we are in a node, whose interval is fully included in [a, b) (the interval which is painted) we just update the colorOf(node) and don't update the left and right subtree. This guarantees we won't color more than O(log R) nodes.

Because of the colors of the nodes we added we should be able to perform some other operations over the tree to keep all the data correct:

• push(node)
• merge(node)

The push operation is used when we enter a node which has colorOf(node) either 0 or 1. We should paint both it's sons with the same color of the parent -- colorOf(left(node)) = colorOf(right(node)) = colorOf(node). To keep correct(node) updated we should check how many of the rows between [from(node), to(node)) are colored in the same color as in the painting. (*1) Then we paint the node with color 2 -- colorOf(node) = 2. The idea of this is the so called "late update". What we actually do is the same as the O(R) update operation, but we just do it when it's really needed to be done.

(*1) This can be done by precomputing the number of ones between rows 0 and i (for all i < R) into an array (numberOnes[i] denoting the number of ones between rows 0 and i) in O(R). Getting the number of ones between rows a and b (excluding b) is just numberOnes[b] - numberOnes[a - 1]. The same can be done for the zeros.

The merge operation is the opposite to the push. Instead of spreading the information from the node to it's sons, it combines the information from the sons and saves it in the parent node. This operation is performed after the recursion is returned into the parent node. In this problem this operation is simple: after a paint() operation returns from updating any (or both) the sons of the current node we set correct(node) = correct(left(node)) + correct(right(node)).

The count() operation is really easy, it is equal to correct(root).

The paint() operation looks like: paint(node, a, b, newColor = {0, 1}) if (colorOf(node) is 2) push(node) if ([from(node), to(node)) is fully included in [a, b)) colorOf(node) = newColor push(node) return paint(left(node), a, b, newColor) if and only if the left son's inteval intersects with [a, b) paint(right(node), a, b, newColor) if and only if the right son's interval intersects with [a, b) merge(node)

This solution has a complexity of O(Q log R), but works only when there is only one column. As there are 15 columns in the worst case we can solve the original problem by using C segment trees, thus the solution is O(CQ log R). Extending the solution from one to C segment trees is easy and left to the reader as a exercise.