Array Game
Contest: Educational Codeforces Round 54 (Rated for Div. 2)
Difficulty rating: 3000
Tags: data structures, games

Consider a following game between two players:

There is an array $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$, consisting of positive integers. Initially a chip is placed into the first cell of the array, and $$$b_1$$$ is decreased by $$$1$$$. Players move in turns. Each turn the current player has to do the following: if the index of the cell where the chip is currently placed is $$$x$$$, then he or she has to choose an index $$$y \in [x, min(k, x + m)]$$$ such that $$$b_y > 0$$$, move the chip to the cell $$$y$$$ and decrease $$$b_y$$$ by $$$1$$$. If it's impossible to make a valid move, the current player loses the game.

Your task is the following: you are given an array $$$a$$$ consisting of $$$n$$$ positive integers, and $$$q$$$ queries to it. There are two types of queries:

- $$$1$$$ $$$l$$$ $$$r$$$ $$$d$$$ — for every $$$i \in [l, r]$$$ increase $$$a_i$$$ by $$$d$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ — tell who is the winner of the game that is played on the subarray of $$$a$$$ from index $$$l$$$ to index $$$r$$$ inclusive. Assume both players choose an optimal strategy.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$, $$$1 \le m \le 5$$$) — the number of elements in $$$a$$$, the parameter described in the game and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — the elements of array $$$a$$$.

Then $$$q$$$ lines follow, each containing a query. There are two types of queries. The query of the first type is denoted by a line $$$1$$$ $$$l$$$ $$$r$$$ $$$d$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le d \le 10^{12}$$$) and means that for every $$$i \in [l, r]$$$ you should increase $$$a_i$$$ by $$$d$$$. The query of the second type is denoted by a line $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) and means that you have to determine who will win the game if it is played on the subarray of $$$a$$$ from index $$$l$$$ to index $$$r$$$ (inclusive).

There is at least one query of type $$$2$$$.

Output format:
For each query of type $$$2$$$ print $$$1$$$ if the first player wins in the corresponding game, or $$$2$$$ if the second player wins.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
5 2 4
1 2 3 4 5
1 3 5 6
2 2 5
1 1 2 3
2 1 5

Example output:
1
1

Example input:
5 1 3
1 1 3 3 4
2 1 5
2 2 5
2 3 5

Example output:
1
2
1

Editorial:
Suppose there is only one query, i. e. we are given some array and we want to know who is the winner if the game is played on this array. One of the obvious solutions is $$$dp[i][x]$$$ — will the current player win if the chip is currently in the cell $$$i$$$ and the number in cell $$$i$$$ is $$$x$$$. We can already see that we don't need to know the exact value of $$$x$$$, we only want to know whether it's odd: if there is a cell $$$j \ne i$$$ such that we can go from $$$i$$$ to $$$j$$$ and $$$dp[j][a_j - 1]$$$ is a state where current player will lose, then we should go to this cell since our opponent will enter a losing state of the game. Otherwise, we want to force our opponent to move out of cell $$$i$$$, and we can do so only if $$$x$$$ is odd. So we found a dynamic programming solution with $$$O(n)$$$ states, but what is more important is that we can take all the elements in our array modulo $$$2$$$.
Okay, now let's solve the problem when there are only queries of type $$$2$$$ (no modifications). Since when calculating the $$$dp$$$ values we are interested only in $$$m$$$ next cells, and there are only $$$2^m$$$ variants of whether these cells are "winning" or "losing", we may consider each element of the array as a function that maps a mask of $$$m$$$ next states into a new mask of $$$m$$$ states if we pushed our new element into the front. For example, if the $$$i$$$-th element is even and states $$$i + 1$$$, $$$i + 2$$$, $$$i + 3$$$, $$$i + 4$$$, $$$i + 5$$$ are winning, losing, losing, winning and losing respectively, and $$$m = 5$$$, then we may consider a mask of next states as $$$10010$$$; and then we can check if $$$i$$$-th state is winning and push a bit to the front of this mask, discarding the last bit; since new state is winning, we will get a mask of $$$11001$$$. It allows us to denote two functions $$$f_0(x)$$$ and $$$f_1(x)$$$ — what will be the resulting mask of next $$$m$$$ states, if current mask is $$$x$$$ and we push an even or odd element to the front.
Okay, what about pushing more than one element? We can just take the composition of their functions! Since a function can be stored as an array of $$$2^m$$$ integers and the composition needs only $$$O(2^m)$$$ time to be calculated, then we can build a segment tree over the elements of the array, and store a composition of all functions on the segment in each node. This allows us to answer queries of type $$$2$$$ in $$$O(2^m \log n)$$$.
The only thing that's left is additions on segment. Adding an even number is easy: just ignore this query. To be able an odd number, let's store another function in each node of the segment tree which would be the composition of all functions on the segment if we would add $$$1$$$ to all elements on the segment (so the elements which were odd become even, and vice versa). This allows us to use lazy propagation: if the query affects the whole node, we may just swap two functions in it and push the query to the children of this node.
Overall complexity is $$$O(2^m (n + q) \log n)$$$. It turns out (we didn't think about it before the contest, but some contestants submitted such solutions) that it can be reduced to $$$O(m (n + q) \log n)$$$ if we will use the distance to closest losing state instead of a mask of winning and losing states.