Problem G
The Ice Cream Game
Kirderf and Slin are early to a great party where ice cream is served to everyone. Right now they are alone in the party hall where $N$ jars of ice cream are placed in a row on a table. There are $K$ different flavours of ice cream, where each flavour is represented by an integer between $0$ and $K - 1$.
Slin and Kirderf have a great ice cream craving and will therefore play a game where they eat some of the ice cream. They will take turns, where a turn consists of eating one jar of ice cream. The party organizers may enter the hall at any moment, so it must not be too obvious that Kirderf and Slin have eaten of the ice cream. Therefore they can only eat the rightmost or leftmost jar of ice cream, so there are no gaps between jars. Also, there must always be at least one jar left of every flavour, or it will be clear that someone has been eating of it. Whoever is unable to make a move loses.
Kirderf doesn’t want to lose against Slin, so he’s asked you to write a program that determines who have a winning strategy at different positions in the game. You will receive $Q$ queries, where each query is an interval $[L, R]$ and your program should determine who has a winning strategy if only jars $L, L + 1, \dots , R$ are left (the jars are numbered from $1$ to $N$ from the left to right).
That a player has a winning strategy means that the player can always win the game no matter what moves the opponent makes. It can be proven that one of the players has a winning strategy.
Input
The first line contains three integers $N$, $K$, $Q$ ($1 \le K \le N \le 2 \times 10^5$, $1 \le Q \le 10^5$). The second line contains $N$ integers, all of them between $0$ and $K - 1$. These describe the flavours of the ice cream jars in the row. Each flavour appears at least once. The next $Q$ lines contains two integers $L_ i$ and $R_ i$ ($1 \le L_ i \le R_ i \le N$).
Output
Output $Q$ lines with one integer for each query. If the player starting for the query $[L_ i, R_ i]$ has a winning strategy, output $1$. If the other player has a winning strategy, output $2$. Finally, if the state is not valid, i.e. if not every ice cream flavour is present in the interval, output $0$.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Constraints |
|
$1$ |
$9$ |
$N,Q \le 15$ |
|
$2$ |
$11$ |
$N,Q \le 100$ |
|
$3$ |
$17$ |
$N,Q \le 1000$ |
|
$4$ |
$5$ |
$K=1$ |
|
$5$ |
$7$ |
$K=2$ |
|
$6$ |
$11$ |
$R_ i - L_ i + 1 \le K+1$ for each $1 \le i \le Q$ |
|
$7$ |
$23$ |
$Q=1$, $L_1=1, R_1=N$ |
|
$8$ |
$17$ |
No additional constraints. |
Explanation of sample 1
For the interval $[1, 5]$ (i.e. all $5$ ice creams remain) the second player has a winning strategy. No matter what the first player does the second player have a possible move, and after that there’s only $3$ jars remaining which means that the first player loses.
For $[1, 4]$ the first player has a winning strategy: removing ice cream $1$.
The interval $[1, 3]$ is not valid since there’s no ice cream jar of flavour $3$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 3 0 0 1 2 0 1 5 1 4 1 3 |
2 1 0 |
