4-й этап Республиканской олимпиады по информатике 2022-2023, 1-й тур


Задача C. Макс MEX

Ограничение по времени:
4 секунды
Ограничение по памяти:
512 мегабайт

Профессор Айдос ведет лекции по информатике в старшей школе. Сегодня он объяснил концепт MEX-а. Напомним, что MEX — это минимальное неотрицательное целое число, которое не представлено в множестве. Примеры: Как талантливый студент, Темирлан решил поспать во время лекции и заметивший это Айдос решил проучить своего талантливого но ленивого студента следующей домашней работой: Он дал Темирлану колоду с $n$ картами. У $i$-карты на лицевой строне написано число $a_i$, а в обратной $b_i$. И дал Темирлану задание в виде $q$ отрезков и для $i$-го отрезка нужно посчитать MEX среди карт $l_i$, $l_i + 1$, $\dots$, $r_i$. Темирлан может переворачивать карты как он хочет и нужно независимо для каждого отрезка найти максимальный МЕХ чисел лицевой стороны. Темирлан решил поспать и попросил вас решить данную задачу за него.
Формат входного файла
В первой строке входных данных задано единственное целое число $n$ ($1 <= n <= 2 \cdot 10^5$) — размер колоды. Во второй строке входных данных задано $n$ целых чисел $a_1$, $a_2$, $\dots$, $a_n$ ($0 <= a_i <= n$) — лица карт. В третьей строке входных данных задано $n$ целых чисел $b_1$, $b_2$, $\dots$, $b_n$ ($0 <= b_i <= n$) — другая сторона карт. В четвертой строке входных данных задано единственное целое число $q$ ($1 <= q <= 2 \cdot 10^5$) — количество отрезков. Затем следуют $q$ строк, в каждой из которой задано два целых числа $l_i$ и $r_i$ ($1 <= l_i <= r_i <= n$).
Формат выходного файла
Для каждого отрезка выведите одно целое число — максимальный МЕХ который можно получить.
Система оценки
Данная задача содержит $7$ подзадач.
Примеры:
Вход
3
1 2 2
1 0 3
3
1 2
1 1
1 3
Ответ
2
0
3
Вход
8
2 1 2 4 0 2 0 0
3 1 0 5 2 5 2 2
13
3 7
2 4
4 8
4 8
1 7
1 7
3 6
4 7
4 5
2 6
4 8
3 5
2 8
Ответ
1
2
1
1
6
6
1
1
1
3
1
1
3
Замечание
В первом примере: Первый запрос $l_1 = 1, r_1 = 2$. Перевернем карты $1$ и $2$, тогда с лицевой стороны видно чисел $1$ и $0$, их MEX равен $2$. Второй запрос $l_2 = 1, r_2 = 1$. С обеих сторон написано число $1$, а MEX $[1]$ равен $0$. Третий запрос $l_3 = 1, r_3 = 3$. Перевернем карты $1$ и $2$, тогда с лицевой стороны видно чисел $1$,$0$ и $2$, их MEX равен $3$. ( Dinmukhamed Tursynbay )
посмотреть в олимпиаде

Комментарий/решение: