루미 알고리즘

#1495플래티넘The Ice Cream Game

PO 2020 온라인 예선코딩출제 Fredrik Ekholm and Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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, …, 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 ≤ K ≤ N ≤ 2 · 10^5, 1 ≤ Q ≤ 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 ≤ L_i ≤ R_i ≤ 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.

GroupPointsConstraints
19N,Q ≤ 15
211N,Q ≤ 100
317N,Q ≤ 1000
45K=1
57K=2
611R_i - L_i + 1 ≤ K+1 for each 1 ≤ i ≤ Q
723Q=1, L_1=1, R_1=N
817No 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 has 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.

예제

예제 1

입력
5 3 3
0 0 1 2 0
1 5
1 4
1 3
출력
2
1
0

출처 표기

출처: Programmeringsolympiaden 2020년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.