Дзеркальна схема#13046

Дзеркальна схема (Розбір)

Розв'язання

Сигнал може перебувати лише у двох станах: $0$ або $1$ .

Тому дію будь-якого відрізка можна описати матрицею розміру $2 \times 2$ 2\times2.

Для матриці $A$ нехай $A [x] [y]$ — максимальна винагорода, яку можна отримати, якщо сигнал входить у відрізок у стані $x$ та виходить із нього у стані $y$ .

Якщо такий перехід неможливий, його значення дорівнює $- \infty$ .

Нехай два сусідні відрізки описуються матрицями $A$ та $B$ .

Тоді їх об'єднання описується max-plus множенням:

(A \otimes B) [x] [z] = y \in {0, 1} max (A [x] [y] + B [y] [z]) .

(A\otimes B)[x][z] = \max_{y\in\{0,1\}} (A[x][y]+B[y][z]).

Таким чином, матриці двох сусідніх відрізків можна об'єднати за сталий час.

Для кожної вершини дерева відрізків будемо зберігати п'ять матриць.

$N$ — жоден елемент не змінено;
$P$ — змінений відрізок починається на лівій межі;
$S$ — змінений відрізок закінчується на правій межі;
$F$ — змінений відрізок знаходиться всередині поточного відрізка;
$W$ — змінено весь поточний відрізок.

Нехай вершина складається з лівого сина $L$ та правого сина $R$ .

Якщо нічого не змінюється, то

N = N_{L} \otimes N_{R} .

N=N_L\otimes N_R.

Для стану $P$ існує два варіанти.

Змінений відрізок може закінчитися всередині лівого сина:

P_{L} \otimes N_{R} .

P_L\otimes N_R.

Або весь лівий син змінений, а відрізок продовжується у правому сині:

W_{L} \otimes P_{R} .

W_L\otimes P_R.

Тому

P = max (P_{L} \otimes N_{R}, W_{L} \otimes P_{R}) .

P= \max( P_L\otimes N_R, W_L\otimes P_R ).

Аналогічно,

S = max (N_{L} \otimes S_{R}, S_{L} \otimes W_{R}) .

S= \max( N_L\otimes S_R, S_L\otimes W_R ).

Для стану $F$ існує п'ять можливостей.

Змінений відрізок повністю знаходиться у лівому сині:

F_{L} \otimes N_{R} .

F_L\otimes N_R.

Або повністю знаходиться у правому сині:

N_{L} \otimes F_{R} .

N_L\otimes F_R.

Він може закінчуватися точно на правій межі лівого сина:

S_{L} \otimes N_{R} .

S_L\otimes N_R.

Або починатися точно на лівій межі правого сина:

N_{L} \otimes P_{R} .

N_L\otimes P_R.

Нарешті, він може перетинати межу між двома синами:

S_{L} \otimes P_{R} .

S_L\otimes P_R.

Отже,

F = max (F_{L} \otimes N_{R}, N_{L} \otimes F_{R}, S_{L} \otimes N_{R}, N_{L} \otimes P_{R}, S_{L} \otimes P_{R}) .

F= \max( F_L\otimes N_R, N_L\otimes F_R, S_L\otimes N_R, N_L\otimes P_R, S_L\otimes P_R ).

Якщо змінюється весь відрізок, то

W = W_{L} \otimes W_{R} .

W=W_L\otimes W_R.

Лист дерева

Для одного елемента нехай $A$ — його матриця переходів для початкового значення $d_{i}$ d_i.

Нехай $B$ — матриця переходів після заміни

d_{i} \leftarrow 9 - d_{i} .

d_i\leftarrow9-d_i.

Тоді

N = A,

N=A,

а

P = S = W = B .

P=S=W=B.

Для відрізка з одного елемента неможливо вибрати непорожній змінений відрізок, який знаходиться строго всередині нього, тому всі значення матриці $F$ спочатку дорівнюють $- \infty$ .

Щоб побудувати матрицю переходів для цифри $d$ , розглянемо обидва можливі початкові стани сигналу.

Якщо

d mod 4 = 0,

d\bmod4=0,

стан змінюється на протилежний.

Якщо

d mod 4 = 1,

d\bmod4=1,

стан не змінюється.

Якщо

d mod 4 = 2,

d\bmod4=2,

стан стає рівним $0$ .

Якщо

d mod 4 = 3,

d\bmod4=3,

стан стає рівним $1$ .

Якщо після проходження елемента сигнал опинився у стані $s$ , отримуємо винагороду $w_{i, s}$ w_{i,s}.

Запити

Для запиту $[l, r]$ [l,r] отримаємо п'ять матриць, що відповідають цьому відрізку, за допомогою дерева відрізків.

Перед позицією $l$ сигнал знаходиться у стані $0$ .

Тому відповіддю буде максимальне значення серед обох можливих кінцевих станів у всіх п'яти матрицях:

N, P, S, F, W .

N,\ P,\ S,\ F,\ W.

Матриця $N$ відповідає випадку, коли ми не виконуємо жодної заміни.

Інші чотири матриці разом покривають усі можливі непорожні відрізки, на яких виконується заміна.

Оновлення

При зміні значення $d_{i}$ d_i перебудовуємо відповідний лист дерева.

Після цього перераховуємо всі вершини на шляху від цього листа до кореня.

Доведення коректності

Кожен можливий змінений відрізок відносно поточного відрізка належить до одного з типів $P$ , $S$ , $F$ або $W$ .

Формули об'єднання розглядають усі можливі положення зміненого відрізка відносно межі між двома синами.

Max-plus множення матриць коректно об'єднує як переходи стану сигналу, так і отримані винагороди для двох послідовних відрізків.

Отже, кожна з п'яти матриць зберігає максимальну винагороду для відповідного типу зміни.

Для запиту ми беремо максимум серед усіх значень, досяжних із початкового стану $0$ , у матрицях $N$ , $P$ , $S$ , $F$ та $W$ .

Це враховує як випадок без заміни, так і кожен можливий непорожній відрізок для заміни.

Тому отримане значення є точно шуканою максимальною винагородою.

Складність

Кожна матриця має сталий розмір, тому об'єднання двох вершин дерева відрізків займає $O (1)$ .

Кожен запит та кожне оновлення обробляють $O (lo g n)$ O(\log n) вершин.

Отже, загальна складність становить

O ((n + q) lo g n)

O((n+q)\log n)

за часом та

O (n)

за пам'яттю.

2 \times 2

(A \otimes B) [x] [z] = y \in {0, 1} max (A [x] [y] + B [y] [z]) .

N = N_{L} \otimes N_{R} .

P_{L} \otimes N_{R} .

W_{L} \otimes P_{R} .

P = max (P_{L} \otimes N_{R}, W_{L} \otimes P_{R}) .

S = max (N_{L} \otimes S_{R}, S_{L} \otimes W_{R}) .

F_{L} \otimes N_{R} .

N_{L} \otimes F_{R} .

S_{L} \otimes N_{R} .

N_{L} \otimes P_{R} .

S_{L} \otimes P_{R} .

F = max (F_{L} \otimes N_{R}, N_{L} \otimes F_{R}, S_{L} \otimes N_{R}, N_{L} \otimes P_{R}, S_{L} \otimes P_{R}) .

W = W_{L} \otimes W_{R} .

d_{i}

d_{i} \leftarrow 9 - d_{i} .

N = A,

P = S = W = B .

d mod 4 = 0,

d mod 4 = 1,

d mod 4 = 2,

d mod 4 = 3,

w_{i, s}

[l, r]

N, P, S, F, W .

d_{i}

O (lo g n)

O ((n + q) lo g n)