Проста підпослідовність (Розбір)

Автор задачі:	Антон Тригуб
Задачу підготували:	Андрій Столітній, Костянтин Денисов
Розбір написав:	Костянтин Луценко

10pt

Блок 1

Ans = R - L + 1 - (L%2==0) - (R%2==0) + ((L==R)&&(L%2==0))

Блок 2

Можна перебрати всі $2^{n}$ 2^n підпослідовностей і перевірити, чи вони є хорошими, порахувавши всі префіксні і суфіксні суми. Можна для кожного з $\frac{n ( n + 1 )}{2}$ \frac{n(n+1)}{2} можливих запитів порахувати відповідь, перебравши всі її підпослідовності. Складність $O (2^{n} \cdot n)$ \mathcal{O}(2^n\cdot n).

Блок 3

Нехай $\sum [L, R]$ \sum [L, R] означає суму на підвідрізку $[L, R]$ . Скажемо, що $\sum [L, R] = d e f 0$ \sum[L, R] \stackrel{def}{=} 0 при $L > R$ L > R (порожній відрізок).

Нехай $\sum [1, n] = S$ \sum[1, n] = S.

Визначення хорошого масиву переписується як $\sum [1, a] ⩾ 0$ \sum[1, a] \geqslant 0, $\sum [a, n] ⩾ 0$ \sum[a, n] \geqslant 0. Але $\sum [a, n] = \sum [1, n] - \sum [1, a - 1]$ \sum[a, n] = \sum[1, n] - \sum[1, a-1]. Тому визначення хорошого масиву можна записати як

$\sum [1, a] \in [0, S]$ \sum[1, a] \in [0, S]

Тому можна обрахувати dp[позиція][поточна сума][максимальна префіксна сума яка зустрічалася], де значення динаміки — це максимальна кількість елементів (або -INF, якщо стан недосяжний). Складність $O (q n^{3})$ \mathcal{O}(q n^3).

Також помітимо, що оптимальна відповідь отримується з заданого відрізка видаленням деякої кількості мінус одиничок. Наша мета — з'ясувати, скільки мінус одиничок ми маємо видалити.

Блок *

Твердження. Масив є хорошим тоді і тільки тоді, коли всі суми його підвідрізків є не більшими за суму всього масиву.

Доведення.

$\Leftarrow$ : Від супротивного, припустимо, всі відрізки мають суму, меншу за $S$ , але масив не є хорошим. Так як масив не є хорошим, то існує або його префікс, або суфікс, з від'ємною сумою. Без обмеження загальності, нехай це префікс, тобто існує $R$ таке, що $\sum [1, R] < 0$ \sum[1, R] < 0. Але тоді $\sum [R + 1, n] = S - \sum [1, R] > S$ \sum[R+1, n] = S - \sum[1, R] > S, тобто відрізок $[1, R]$ має суму більшу за суму всього масиву.

$\Rightarrow$ : Від супротивного, припустимо, що масив є хорошим, але існує $\sum [L, R] > \sum [1, n]$ \sum[L, R] > \sum[1, n]. Тому $\sum [1, n] - \sum [L, R] = \sum [1, L - 1] + \sum [R + 1, n] < 0$ \sum[1, n] - \sum[L, R] = \sum[1, L-1] + \sum[R+1, n] < 0, тому хоча б одне з чисел $\sum [1, L - 1]$ \sum[1, L-1] або $\sum [R + 1, n]$ \sum[R+1, n] є від'ємним, бо їх сума від'ємна. Отже, масив не є хорошим.

Повернемось до задачі — потрібно визначити мінімальну кількість «-1», яку потрібно видалити, щоб суми на всіх підвідрізках не перевищували суму на всьому масиві.

Нехай $\sum [1, n] = S_{0}$ \sum[1, n] = S_0. Нехай $[L, R]$ — це підвідрізок з максимальною сумою (якщо таких декілька, то довільний з них). Нехай $\sum [L, R] = M_{0}$ \sum[L, R] = M_0. Хочемо зробити, щоб $S = M$ S = M, але спочатку маємо $M_{0} ⩾ S_{0}$ M_0 \geqslant S_0.

За одне видалення мінус одинички $S$ збільшується на 1, а $M$ не зменшується. Отже, різниця $M - S$ M - S зменшується не більше, ніж на 1. Отже, ми маємо видалити щонайменше $M_{0} - S_{0}$ M_0-S_0 елементів.

Доведемо, що $M_{0} - S_{0}$ M_0-S_0 елементів видалити завжди достатньо. Нехай $\sum [1, L - 1] = - P$ \sum[1, L-1] = -P і $\sum [R + 1, n] = - Q$ \sum[R+1, n] = -Q. Помітимо, що $M_{0} - S_{0} = \sum [L, R] - \sum [1, n] = - (\sum [1, L - 1] + \sum [R + 1, n]) = P + Q$ M_0-S_0 = \sum[L, R] - \sum[1, n] = -(\sum[1, L-1] + \sum[R+1, n]) = P + Q. Помітимо також, що $P, Q ⩽ 0$ P, Q \leqslant 0 (тобто $\sum [1, L - 1] ⩽ 0$ \sum[1, L-1] \leqslant 0 та $\sum [R + 1, n] ⩽ 0$ \sum[R+1, n] \leqslant 0), бо інакше $[L, R]$ можна розширити зі збільшенням суми.

Нехай $\sum^{'} [L, R]$ \sum'[L, R] — це сума на підвідрізку після нашого видалення. Ми хочемо зробити, щоб тепер всі суми $\sum^{'} [1, a]$ \sum'[1, a] та $\sum^{'} [a, n]$ \sum'[a, n] були невід'ємнии, видаливши $P + Q$ P+Q мінус одиничок.

Для цього видалимо на префіксі $[1, L - 1]$ [1, L-1] деякі $P$ мінус одиничок, а на суфіксі $[R + 1, n]$ [R+1, n] деякі $Q$ мінус одиничок. Які саме — з'ясуємо пізніше. Тоді $\sum^{'} [1, L - 1] = \sum [1, L - 1] + P = - P + P = 0$ \sum'[1, L-1] = \sum[1, L-1] + P = -P+P = 0, аналогічно $\sum^{'} [R + 1, n] = 0$ \sum'[R+1, n] = 0.

Помітимо, що $\sum [a + 1, L - 1] ⩽ 0$ \sum[a+1, L-1] \leqslant 0, бо інакше $\sum [a + 1, R] = \sum [L, R] + \sum [a + 1, L - 1] > \sum [L, R]$ \sum[a+1, R] = \sum[L, R] + \sum[a+1, L-1] > \sum[L, R], а ми позначили $[L, R]$ відрізок з найбільшою сумою.

Помітимо, що $\sum [L, a] ⩾ 0$ \sum[L, a] \geqslant 0, бо інакше $\sum [a + 1, R] = \sum [L, R] - \sum [L, a] > \sum [L, R]$ \sum[a+1, R] = \sum[L, R] - \sum[L, a] > \sum[L, R], а ми позначили $[L, R]$ відрізок з найбільшою сумою.

Визначимо, які додаткові умови необхідні для того, щоб отриманий масив був хорошим:

$a < L$ a < L:
З'являється умова $\sum^{'} [1, a] ⩾ 0$ \sum'[1, a] \geqslant 0.
$L ⩽ a ⩽ R$ L \leqslant a \leqslant R:
$\sum^{'} [1, a] = \sum^{'} [1, L] + \sum^{'} [L, a] = 0 + \sum^{'} [L, a] ⩾ 0$ \sum'[1, a] = \sum'[1, L] + \sum'[L, a] = 0 + \sum'[L, a] \geqslant 0,
тобто це виконується автоматично.
$a > R$ a > R:
$\sum^{'} [1, a] = \sum^{'} [1, L - 1] + \sum^{'} [L, R] + \sum^{'} [R + 1, a] =$ \sum'[1, a] = \sum'[1, L-1] + \sum'[L, R] + \sum'[R+1, a] =
$= 0 + M_{0} + \sum^{'} [R + 1, a] = M_{0} + \sum^{'} [R + 1, n] - \sum^{'} [a + 1, n] =$ = 0 + M_0 + \sum'[R+1, a] = M_0 + \sum'[R+1, n] - \sum'[a+1, n] =
$= M_{0} + 0 - \sum^{'} [a + 1, n]$ =M_0 + 0 - \sum'[a+1, n],
тобто з'являється умова $\sum^{'} [a + 1, n] ⩽ M_{0}$ \sum'[a+1, n] \leqslant M_0.

Отже, необхідно і достатньо, щоб для всіх $a < L$ a < L виконувалось $\sum [1, a] \in [0, M_{0}]$ \sum[1, a] \in [0, M_0], а також аналогічна умова на суфікси, тобто $\sum [a, n] \in [0, M_{0}]$ \sum[a, n] \in [0, M_0] для всіх $a > R$ a > R. Цього, наприклад, можна добитися, якщо видаляти «-1» жадібно: йдемо по $[1.. a]$ збільшуючи $a$ від $0$ до $L - 1$ L-1 і, якщо префіксна сума стала від'ємна, то видаляємо поточну мінус одиницю. Тоді всі префіксні суми стануть невід'ємні. Припустимо, що при видаленні одиниці на позиції $a$ виявилось, що $\sum^{'} [1, b]$ \sum'[1, b] стала більшою за $M_{0} + 1$ M_0 + 1 для деякого $b < L$ b < L. Помітимо, що в цей момент змінились тільки префіксні суми, що правіше за $a$ , тобто $b ⩾ a$ b \geqslant a. Але $\sum^{'} [1, a]$ \sum'[1, a] у цей момент стала рівною $0$ . Тому $\sum^{'} [a + 1, b] = \sum^{'} [1, b] - \sum^{'} [1, a] = M_{0} + 1$ \sum'[a+1, b] = \sum'[1, b] - \sum'[1, a] = M_0 + 1. Але на цьому відрізку ми нічого не змінювали, тобто

$\sum^{'} [a + 1, b] = \sum [a, b] = M_{0} + 1 > M_{0} = \sum [L, R]$ \sum'[a+1, b] = \sum[a, b] = M_0 + 1 > M_0 = \sum[L, R].

Але ми обирали $M_{0}$ M_0 як максимальну суму на підвідрізку. Тому такого не може бути, а значить, всі префіксні суми лежать у потрібних межах. Аналогічно робимо з суфіксами.

Також варто зауважити, що ми дійсно видалили рівно $P$ мінус одиничок, тобто що сума на всьому префіксі стала рівною нулеві. Дійсно, якщо при видаленні мінус одинички з позиції $a$ виявилось, що $\sum^{'} [1, L - 1] > 0$ \sum'[1, L-1] > 0, то $\sum [a + 1, L - 1] = \sum^{'} [a + 1, L - 1] = \sum^{'} [1, L - 1] - \sum^{'} [1, a] = \sum^{'} [1, L - 1] - 0 > 0$ \sum[a+1, L-1] = \sum'[a+1, L-1] = \sum'[1, L-1] - \sum'[1, a] = \sum'[1, L-1] - 0 > 0, а ми доводили, що суми на відрізках виду $[a, L - 1]$ [a, L-1] завжди невід'ємні.

Отже, ми звели задачу до пошуку $M_{0}, S_{0}$ M_0, S_0 і виведення на екран величини $R - L + 1 - (M_{0} - S_{0})$ R - L + 1 - (M_0 - S_0).

Блок 4

В розборі цього і наступних блоків описано, як знайти $M = l ⩽ L ⩽ R ⩽ r max \sum [L, R]$ M = \max\limits_{l\leqslant L \leqslant R \leqslant r}\sum[L, R]. Як показано вище, це розв'яже задачу.

Переберемо $R$ . Маємо обрати $L$ таке, що $\sum [L, R]$ \sum[L, R] максимальне, тобто $\sum [1, L - 1]$ \sum[1, L-1] мінімальне. Можемо підтримувати це $L$ одночасно з перебором $R$ .

Складність: $O (q n)$

Блоки 5-6

Нехай $n o d e [L, R]$ node[L, R] — це четвірка значень:

$S$ — сума на цьому відрізку;
$A$ — максимальна сума префіксу цього відрізку;
$B$ — максимальна сума суфікса цього відрізку;
$M$ — максимальна сума деякого підвідрізку цього відрізку.

Тоді можна рахувати $n o d e [L, R]$ node[L, R] через $n o d e [L, a]$ node[L, a] та $n o d e [a + 1, R]$ node[a+1, R] для деякого $a$ : нехай

$(S_{1}, A_{1}, B_{1}, M_{1}) + (S_{2}, A_{2}, B_{2}, M_{2}) = (S, A, M, B)$ (S_1, A_1, B_1, M_1) + (S_2, A_2, B_2, M_2) = (S, A, M, B),

тоді:

$S = S_{1} + S_{2}$ S = S_1 + S_2;
$A = max (A_{1}, S_{1} + A_{2})$ A = \max(A_1, S_1 + A_2);
$B = max (B_{2}, S_{2} + B_{1})$ B = \max(B_2, S_2 + B_1);
$M = max (M_{1}, M_{2}, B_{1} + A_{2})$ M = \max(M_1, M_2, B_1 + A_2).

Якщо ви дуже хочете здати ці блоки, але не здати наступний, можна використати sqrt-декомпозицію за $O (q n)$ \mathcal{O}(q\sqrt{n}). Для цього слід розділити масив на блоки довжини $C$ (де $C \sim n$ C \sim \sqrt{n}) і підрахувати $n o d e [k C, (k + 1) C - 1]$ node[kC, (k+1)C-1]. Далі для кожного запиту пошуку відповіді можна виконувати $O (n / C)$ описаних вище злиттів, а для запитів оновлення потрібно перераховувати суму для зміненого блоку за $O (C)$ .

Блок 7

Описане в попередньому блоці злиття можна обраховувати в дереві відрізків, у вершинах якого будуть зберігатись числа $S, A, B, M$ S, A, B, M для відповідних відрізків. Запит get також буде використовувати дане злиття і поверне четвірку чисел, з якої ми візьмемо $M$ та $S$ і виведемо $R - L + 1 - (M - S)$ R - L + 1 - (M - S).