Это сложная версия задачи. В двух версиях отличаются ограничения на \(q\) и ограничение по времени отличаются. В этой версии \(0 \leq q \leq 2 \cdot 10^5\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Команда, состоящая из \(n\) участников, пронумерованных от \(1\) до \(n\), должна представить слайд-шоу на большом собрании. Слайд-шоу содержит \(m\) слайдов.
Имеется массив \(a\) длины \(n\). Изначально участники собрания стоят в очереди в порядке \(a_1, a_2, \ldots, a_n\) от начала до конца. Слайд-шоу состоит из последовательного показа слайдов с \(1\) по \(m\). Каждый слайд будет представлен участником, стоящим в начале очереди. После представления каждого слайда вы можете переместить участника, стоящего в начале очереди, на любую позицию в очереди (без изменения порядка остальных участников). Например, предположим, что очередь участников имеет вид \([\color{red}{3},1,2,4]\). После того как участник \(3\) представит текущий слайд, вы можете изменить очередь участников на \([\color{red}{3},1,2,4]\), \([1,\color{red}{3},2,4]\), \([1,2,\color{red}{3},4]\) или \([1,2,4,\color{red}{3}]\).
Также имеется массив \(b\) длины \(m\). Слайд-шоу считается хорошим, если можно так перемещать участников после выступлений, чтобы слайд \(i\) был представлен участником \(b_i\) для всех \(i\) от \(1\) до \(m\).
Однако ваш назойливый начальник хочет сделать \(q\) обновлений массива \(b\). В \(i\)-м обновлении он выберет слайд \(s_i\) и участника \(t_i\) и присвоит \(b_{s_i} := t_i\). Заметим, что эти обновления постоянны, то есть изменения, внесенные в массив \(b\), будут применяться при обработке последующих обновлений.
Для каждого из \(q+1\) состояний массива \(b\) (начального состояния и после каждого из \(q\) обновлений) определите, является ли слайд-шоу хорошим.
Выходные данные
Для каждого набора входных данных выведите \(q+1\) строку, соответствующих \(q+1\) состоянию массива \(b\). Выведите «YA», если слайд-шоу хорошее, и «TIDAK» в противном случае.
Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «YA», «Ya», «ya» и «YA» будут распознаны как положительные ответы.
Примечание
В первом наборе входных данных изначально вам не нужно перемещать участников, так как оба слайда будут представлены участником \(1\), который уже находится в начале очереди. После этого присваивается \(b_1 := 2\), теперь слайд \(1\) должен быть представлен участником \(2\). Это невозможно, так как участник \(1\) представит слайд \(1\) первым. Затем устанавливается \(b_1 = 1\), \(b\) становится таким же, как и начальный \(b\), что делает слайд-шоу хорошим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2 2
1 2 3 4
1 1
1 2
1 1
3 6 2
1 2 3
1 1 2 3 3 2
3 3
2 2
4 6 2
3 1 4 2
3 1 1 2 3 4
3 4
4 2
|
YA
TIDAK
YA
YA
TIDAK
YA
TIDAK
YA
YA
|