Subtask 1

There are only query events in this subtask. Let's figure out how to perform queries in ~\mathcal{O}(1)~ or ~\mathcal{O}(\log n)~ time.

The first observation to make is that we only care about the parity of the final expression, so all values ~a_i~ can be taken modulo ~2~. Since multiplication is done before addition, it is useful to break up the expression at addition signs and consider each "block" of multiplication signs as a single unit.

Because all values are taken modulo ~2~, if there is at least one even number (which is congruent to ~0 \pmod{2}~) in a block of multiplication signs, the entire block will equal an even number. If and only if all numbers inside a multiplication block are odd (congruent to ~1 \pmod{2}~), then the block will equal an odd number.

Now, when we add multiplication blocks together, the pairty of the expression will only change when adding an odd multiplication block. The parity of the entire expression is simply the parity of the number of odd multiplication blocks.

Okay, but how do we perform queries? Well, consider how brackets break up the expression into several parts. The opening and closing brackets may split multiplication blocks into two pieces:

~ \begin{matrix} \dots &+ &\boxed{\qquad\ \ \ \, \text{left block}\qquad\ \ \ \, } &+ &\dots& + &\boxed{\qquad\ \ \,\text{right block}\qquad\ \ \,} &+ &\dots & & \text{Before}\\ \dots &+ &\boxed{\text{LL mult}} \times \bigg( \boxed{\text{LR mult}} &+ &\dots& + &\boxed{\text{RL mult}} \bigg) \times \boxed{\text{RR mult}} &+ &\dots & & \text{After} \end{matrix} ~

The rest of the expression is unaffected. Thus, we must evaulate the parity of these four new multiplication blocks by checking if they contain at least one even number. Note that some of these new blocks may not contain any numbers at all (e.g. if the brackets land on the edge of a multiplication block). This can be done with a prefix sum array which counts even numbers. As for determining the parity of the ... regions, this can be done with a prefix sum array on the multiplication blocks, modulo ~2~. To determine which multiplication block the left and right brackets fall into, we can either preprocess the block ids for every index, or binary search on a sorted list of endpoints defining the multiplication block intervals.

Time Complexity: ~\mathcal{O}(N + Q)~ or ~\mathcal{O}(N + Q \log N)~

Subtask 2

This subtask requires our implementation to support updates. Thus, we can take our Subtask 1 solution and replace the prefix sum arrays with Binary Indexed Trees. Preprocessing block ids will no longer work, so using a sorted set of endpoints and binary searching will suffice. Here are some notes on implementation:

V - Value update:

• Update the even counting BIT
• Binary search on set of endpoints to determine the block that this value belongs to
• Check if the block has changed parity by querying the even counting BIT
• If so, update the block sum BIT accordingly

O - Operator Update:

+ ~\to~ x

• Merge two multiplication blocks
• Remove old endpoints from set and add combined block to set of endpoints
• Query even counting BIT to determine parity of merged block (or just multiply the parities of the two old blocks)
• Clear old values from block sum BIT and update with new value

x ~\to~ +

• Split a multiplication block
• Binary search set of endpoints to determine which block is being split
• Remove it from the set and then add the two new blocks to the set of endpoints
• Query the even counting BIT to determine the parity of each new block
• Clear the old value from block sum BIT and update with two new values accordingly

Time Complexity: ~\mathcal{O}((N + Q) \log N)~

Alternate Solution

An alternate solution involves building a segment tree with the following information stored in each node:

• Total parity
• Prefix multiplication block parity
• Suffix multiplication block parity
• Whether or not the entire range is multiplication

When combining nodes, case work must be done on the operation between the two nodes. The rest of the implementation is left as an exercise for the reader.

Time Complexity: ~\mathcal{O}((N + Q) \log N)~