Префіксні MEX#12785

Префіксні MEX (Розбір)

Автор задачі:	Мар'ян Шийка
Підготував:	Мар'ян Шийка
Розбір:	Мар'ян Шийка

Ідея

Нехай

b = [a_{L}, a_{L + 1}, \dots, a_{R}] .

b=[a_L,a_{L+1},\ldots,a_R].

Для зручності переведемо межі запиту $[l, r]$ [l,r] у координати початкового масиву:

X = L + l - 1, Y = L + r - 1.

X=L+l-1,\qquad Y=L+r-1.

Розглянемо окремо випадки $k = 1$ k=1, $k = 2$ k=2 та $k \geq 3$ k\ge 3.

$k = 1$ k=1

Для поточного значення $L$ підтримуватимемо масив

c_{i} = f ([a_{L}, a_{L + 1}, \dots, a_{i}]) .

c_i=f([a_L,a_{L+1},\ldots,a_i]).

Для $L = 1$ L=1 цей масив можна побудувати звичайним проходом зліва направо, підтримуючи поточний MEX.

Розглянемо перехід від $L$ до $L + 1$ L+1. Нехай

v = a_{L} .

v=a_L.

Позначимо через $p$ наступну після $L$ позицію, на якій зустрічається значення $v$ . Якщо такої позиції немає, покладемо $p = n + 1$ p=n+1.

Після видалення $a_{L}$ a_L значення prefix MEX можуть змінитися лише до наступного входження $v$ , тобто на позиціях до $p - 1$ p-1.

Нехай $x$ — перша позиція, для якої

c_{x} > v .

c_x>v.

Тоді після переходу до $L + 1$ L+1 на всьому відрізку

[x, p - 1]

[x,p-1]

новий prefix MEX дорівнюватиме $v$ . Отже, потрібно виконати операцію

c_{i} = v

c_i=v

для всіх $i \in [x, p - 1]$ i\in[x,p-1].

Для підтримки масиву $c$ використаємо дерево відрізків, яке вміє:

присвоювати одне значення всім елементам на відрізку;
знаходити суму на відрізку;
знаходити першу позицію $x$ , для якої $c_{x} > v$ c_x>v.

Тоді відповідь на запит з $k = 1$ k=1 дорівнює

i = X \sum Y c_{i} .

\sum_{i=X}^{Y}c_i.

$k = 2$ k=2

Нехай

d = f (c) .

d=f(c).

Оскільки масив $c$ є неспадним, значення $d$ збільшується на одиницю щоразу, коли в $c$ вперше з'являється наступне необхідне значення

0, 1, 2, \dots

0,1,2,\ldots

Позначимо через $p_{x}$ p_x першу позицію, на якій у $c$ з'являється значення $x$ .

Число $x$ впливає на відповідь лише тоді, коли перші входження утворюють ланцюжок

p_{0} < p_{1} < \dots < p_{x} .

p_0<p_1<\ldots<p_x.

У такому випадку поява $x$ збільшує prefix MEX на всіх позиціях починаючи з $p_{x}$ p_x. Тобто вона відповідає операції

d_{i} \leftarrow d_{i} + 1

d_i\gets d_i+1

для всіх

i \in [p_{x}, n] .

i\in[p_x,n].

Тому масив $d$ можна підтримувати другим деревом відрізків, яке підтримує додавання на відрізку та знаходження суми на відрізку.

При переході від $L$ до $L + 1$ L+1 змінюється структура перших входжень, а разом з нею може змінитися початковий строго зростаючий ланцюжок

p_{0} < p_{1} < p_{2} < \dots

p_0<p_1<p_2<\ldots

Якщо деякі значення починають належати цьому ланцюжку, для них додаємо відповідні операції

[p_{x}, n] \leftarrow + 1.

[p_x,n]\gets +1.

Якщо деякі значення перестають йому належати, виконуємо

[p_{x}, n] \leftarrow - 1.

[p_x,n]\gets -1.

Ці зміни можна підтримувати амортизовано, тому сумарна кількість оновлень протягом усього проходу за $L$ є лінійною.

Тоді відповідь на запит з $k = 2$ k=2 дорівнює

i = X \sum Y d_{i} .

\sum_{i=X}^{Y}d_i.

$k \geq 3$ k\ge 3

Після третього застосування операції $f$ масив гарантовано стає константним.

Якщо $a_{L} = 0$ a_L=0, то перший елемент $f (b)$ дорівнює $1$ , тому в $f (b)$ взагалі немає нуля. Отже,

f^{2} (b) = [0, 0, \dots, 0],

f^2(b)=[0,0,\ldots,0],

а

f^{3} (b) = [1, 1, \dots, 1] .

f^3(b)=[1,1,\ldots,1].

Якщо $a_{L} \neq = 0$ a_L\ne0, то перший елемент $f (b)$ дорівнює $0$ . Після ще одного застосування $f$ усі елементи отриманого масиву додатні, тому

f^{3} (b) = [0, 0, \dots, 0] .

f^3(b)=[0,0,\ldots,0].

Далі кожне застосування $f$ просто змінює константний масив з нулів на константний масив з одиниць і навпаки.

Таким чином, для $k \geq 3$ k\ge3

g (k, b) = [1, 1, \dots, 1]

g(k,b)=[1,1,\ldots,1]

тоді і тільки тоді, коли

(a_{L} = 0) XOR (k mod 2 = 0) .

(a_L=0)\mathbin{\mathrm{XOR}}(k\bmod 2=0).

В іншому випадку

g (k, b) = [0, 0, \dots, 0] .

g(k,b)=[0,0,\ldots,0].

Отже, відповідь на запит з $k \geq 3$ k\ge3 дорівнює або

r - l + 1,

r-l+1,

або $0$ .

Складність

Обробляємо значення $L$ послідовно від $1$ до $n$ .

Для $k = 1$ k=1 кожен перехід виконується за $O (lo g n)$ O(\log n).

Для $k = 2$ k=2 кожне оновлення дерева відрізків займає $O (lo g n)$ O(\log n), а сумарна кількість необхідних змін є амортизовано лінійною.

Кожен запит з $k = 1$ k=1 або $k = 2$ k=2 обробляється за $O (lo g n)$ O(\log n), а запит з $k \geq 3$ k\ge3 — за $O (1)$ .

Отже, загальна асимптотика — $O ((n + q) lo g n)$ O((n+q)\log n).

Використання пам'яті — $O (n + q)$ O(n+q).

b = [a_{L}, a_{L + 1}, \dots, a_{R}] .

[l, r]

X = L + l - 1, Y = L + r - 1.

k = 1

k = 2

k \geq 3

k = 1

c_{i} = f ([a_{L}, a_{L + 1}, \dots, a_{i}]) .

L = 1

L + 1

v = a_{L} .

p = n + 1

a_{L}

p - 1

c_{x} > v .

L + 1

[x, p - 1]

c_{i} = v

i \in [x, p - 1]

c_{x} > v

k = 1

i = X \sum Y c_{i} .

k = 2

d = f (c) .

0, 1, 2, \dots

p_{x}

p_{0} < p_{1} < \dots < p_{x} .

p_{x}

d_{i} \leftarrow d_{i} + 1

i \in [p_{x}, n] .

L + 1

p_{0} < p_{1} < p_{2} < \dots

[p_{x}, n] \leftarrow + 1.

[p_{x}, n] \leftarrow - 1.

k = 2

i = X \sum Y d_{i} .

k \geq 3

a_{L} = 0

f^{2} (b) = [0, 0, \dots, 0],

f^{3} (b) = [1, 1, \dots, 1] .

a_{L} \neq = 0

f^{3} (b) = [0, 0, \dots, 0] .

k \geq 3

g (k, b) = [1, 1, \dots, 1]

(a_{L} = 0) XOR (k mod 2 = 0) .

g (k, b) = [0, 0, \dots, 0] .

k \geq 3

r - l + 1,

k = 1

O (lo g n)

k = 2

O (lo g n)

k = 1

k = 2

O (lo g n)

k \geq 3

O ((n + q) lo g n)

O (n + q)