Змінимо порядок сумування — замість обчислення суми ваг усіх розбиттів, порахуємо суму для всіх відрізків, який внесок до відповіді вони дають.
Відрізок \([i, j]\) дає внесок \(|s_j - s_{i-1}| \cdot f_{i-1} \cdot g_j\), де \(s_k\) — часткова сума масиву, \(f_k\) — кількість способів розбити масив на підмасиви зліва від позиції \(k\), а \(g_k\) — кількість способів розбити справа від позиції \(k\).
Якщо \(s_{i-1} < s_j\), то внесок відрізка дорівнює \((s_j - s_{i-1}) \cdot f_{i-1} \cdot g_j = (s_j \cdot g_j) \cdot f_{i-1} - g_j \cdot (s_{i-1} \cdot f_{i-1})\). Якщо ж \(s_{i-1} \ge s_j\), то внесок буде зі знаком «мінус».
Будемо підтримувати два дерева Фенвіка (або дерева відрізків): одне для суми значень \(f_i\), інше — для суми значень \(s_i \cdot f_i\).
Посортуємо індекси за зростанням значень \(s_i\). Переберемо індекси \(j\) в такому порядку. Знайдемо суму внесків усіх відрізків, що закінчуються в позиції \(j\). Для цього знайдемо відповідні суми \(f_i\) та \(s_i \cdot f_i\) на префіксі в деревах Фенвіка, додамо суму внесків до відповіді, та оновимо дерева Фенвіка.
У цій задачі потрібно було реалізувати те, що сказано в умові.
С. Сума XOR-ів на всіх підвідрізках
Задачу можна розв’язувати незалежно для кожного біта. Відтепер будемо вважати, що \(a_i\) можуть набувати лише значень \(0\) і \(1\).
\(f(a)\) дорівнює кількості відрізків з непарною кількістю одиниць. Нехай \(c_0\) — кількість префіксів масиву з парною кількістю одиниць, а \(c_1\) — з непарною. Тоді \(f(a) = c_0 \cdot c_1\).
Будемо підтримувати дерево відрізків, де для кожного біта будемо у вершині підтримувати \(c_0\) і \(c_1\).
Складність: \(O(n \log n \log A)\), де \(A\) — максимальне значення \(a_i\).
Розіб’ємо масив на блоки, позиціями \(i\) такими, що \(a_i > a_{i + 1}\). Нехай розміри блоків — \(b_1, b_2, \dots, b_x\). Тоді підмасив є хорошим, якщо:
він повністю лежить всередині одного блокy. Таких підмасивів є \(\sum_i \frac {b_i (b_i + 1)} 2\).
підмасив лежить всередині двох сусідніх блоків. Їх буде рівно \(\sum b_i \cdot b_{i + 1}\).
Тому відповідь — сума двох порахованих значень.
Щоб верхні кінці паличок лежали на одній прямій, кінцеві координати паличок повинні утворювати арифметичну прогресію, тобто \(y_i = k \cdot i + b\), де \(k\) і \(b\) — деякі цілі параметри.
Ціна, яку потрібно заплатити дорівнює \[\sum_{i=1}^n |x_i - y_i| = \sum_{i=1}^n |x_i - k \cdot i - b|.\]
Ця функція від двох змінних \(k\) і \(b\) є опуклою вниз.
Зробимо трійковий пошук за змінною \(k\).
Позначимо \(z_i = x_i - k \cdot i\). Потрібно знайти мінімальне значення \[\sum_{i=1}^n |z_i - b|.\]
Мінімальне значення досягається, коли \(b\) дорівнює медіані масиву \(z\).
Розв’яжемо задачу методом динамічного програмування.
Визначимо хорошими листками, ті листки значення \(x\) яких є найменшим серед всіх листків.
Нехай:
\(\text{dp}[v][0]\) — кількість обходів які може повернути функція \(\text{RFS}(v)\), якщо вона запускається тільки для вершин піддерева вершини \(v\), та остання вершина обходу не є хорошим листком.
\(\text{dp}[v][1]\) — кількість обходів які може повернути функція \(\text{RFS}(v)\), якщо вона запускається тільки для вершин піддерева вершини \(v\), та остання вершина обходу є хорошим листком.
Оскільки для будь якого обходу кожна вершина буде іти після всіх її предків, \(\text{dp}[v][k]\) можна перераховувати за допомогою значень його синів.
Кількість обходів, які є об’єднанням двох вершин \(v\) та \(u\) рівна:
\(\binom{\text{size}_v + \text{size}_u - 1}{\text{size}_u} \cdot \text{dp}[v][0] \cdot (\text{dp}[u][0] + \text{dp}[u][1])) + \binom{\text{size}_v + \text{size}_u - 1}{\text{size}_v} \cdot \text{dp}[u][0] \cdot (\text{dp}[v][0] + \text{dp}[v][1])\), для випадку коли остання вершина не є хорошим листком
\(\binom{\text{size}_v + \text{size}_u - 1}{\text{size}_u} \cdot \text{dp}[v][1] \cdot (\text{dp}[u][0] + \text{dp}[u][1])) + \binom{\text{size}_v + \text{size}_u - 1}{\text{size}_v} \cdot \text{dp}[u][1] \cdot (\text{dp}[v][0] + \text{dp}[v][1])\), для випадку коли остання вершина є хорошим листком
Де \(\text{size}_v\) та \(\text{size}_u\) є кількістю вершин у піддереві вершин \(v\) та \(u\) відповідно.
Об’єднувати більше ніж 2 сини, можна аналогічно, поступово додаючи їх до \(\text{dp}\) їх батька.
Складність обрахунку цієї динаміки рівна \(O(n)\).
Якщо підрахувати її для кожного можливого кореня то отримаємо всі відповіді, таке рішення матиме складність \(O(n^2)\). Але підрахувавши \(\text{dp}\) один раз для певного кореня, можна використати техніку "зміни кореня" (rerooting tree dp) можна знайти всі відповіді зі складність \(O(n)\).
Випадок коли є тільки один хороший листок потрібно розглянути окремо, бо для обходу який починається з нього хорошими листками будуть ті характеристики який є другими найменшими.
Слабкозв’язний орієнтований граф, у якого з кожної вершини виходить рівно одне ребро завжди складається рівно з одного циклу та шляхів, що ведуть до нього. Таким чином, найбільшою компонентою сильної звязності і буде цикл.
Почнімо у вершини 1. Далі, для кожної наступний вершини \(u\), подивимось чи існує шлях від поточної вершини до \(u\), якщо так — продовжимо з вершиною \(u\), інакше залишимось у тій самій вершині і продовжимо процедуру.
Після проведених операцій, останньою відвіданою вершиною буде точно вершина цикла, більше того серед відвіданих вершин точно зустрінуться всі вершини циклу. Тому ми можемо запустити бінарний пошук на масиві відвіданих вершин та знайти першу вершину циклу, яку ми відвідали (всі вершини після неї і будуть шуканим циклом).
Для того, щоб перевірити чи вершина \(x\) належить циклу, помітимо, що з вершини на циклі можна дістатись тільки до інших вершин циклу, тому достатньо перевірити існування шляху від останньої відвіданої вершини до \(x\).
Таким чином, ми витратимо \(n\) запитів на перший обхід та \(\log n\) запитів на бінарний пошук.
Переберемо вершину \(x\) із другого дерева. Нехай ця вершина є корнем сонця в ньому. Нехай \(S_x\) — множина всіх сусідів у другому дереві \(x\), разом з самою вершиною \(x\). Тоді кожна підмножина \(S_x\), яка включає в себе \(x\) буде утворювати сонце.
Тоді подивимось на вершини \(S_x\) у першому дереві, та виберемо найдовший шлях, який включає в себе вершину \(x\).
Це можна реалізувати досить швидко оскільки \(\sum_x |S_x| = n + 2 \cdot E = O(n)\), де \(E = n - 1\) — кількість ребер другого графу.
Для того, щоб створити дерево \(T\), що складється з ребер першого дерева між вершинами \(S_x\), можна розглянути масив предків вершин з першого дерева \(p\). Тоді для вершини \(v \in S_x\), додати ребро \((p_v, v)\) до \(T\) якщо \(p_v \in S_x\). Після цього достатньо знайти найдовший шлях в \(T\), що включає вершину \(x\).
Побудуємо граф, у якому кожною вершинами будуть числа \(0, \dots, m - 1\). Між вершинами \(u, v\) буде існувати ребро, яке рівне найменшій можливій ціні операції, що може зробити з числа \(u\), число \(v\) по модулю \(m\) або \(\infty\) якщо такої операції не існує. Цей граф можна побудувати за \(O(m ^ 2 + q \cdot m)\).
Тепер для кожного \(i = 0 \dots m - 1\), необхідно знайти шлях мінімальної сумарної ваги з вершини \(1\) до вершини \(i\) довжини рівно \(k\).
Для цього скористаймося чимось подібним до бінарного піднесення матриць. Нехай матриця \(A^k\) - така, що \(A_{i, j} ^ k\) — мінімальна вага шляху довжини рівно \(k\) з вершини \(i\) до вершини \(j\). \(A^1\) тоді — це матриця сусідності графу.
Тоді маючи дві матриці \(A ^ {k_1}\) та \(A ^ {k_2}\), ми можемо знайти матрицю мінімальних ваг для шляху довжини \(k_1 + k_2\), наступною операцією:
\(A^{k_1 + k_2}_{i, j} = \min_t A^{k_1}_{i, t} + A^{k_2}_{t, j}\).
Позначимо цю операцію, як \((\min, +)\)-добуток матриць.
Тоді, щоб знайти матрицю \(A^k\), розглянемо випадки відносно \(k\):
якщо \(k = 0\), відповіддю буде матриця, в якій\(A^0_{i, j}\) рівне \(\infty\), якщо \(i \neq j\) та \(0\), інакше.
якщо \(k\) — парне, то \(A^k = A^{\frac k 2}\ (\min, +)\ A^{\frac k 2}\).
інакше, \(A^k = A\ (\min, +)\ A ^ {k - 1}\).
Тобто \(A^k\) можна знайти аналогічно алгоритму бінарного піднесення до степеню в часі \(O(m ^ 3 \log k)\). Таким чином загальний час роботи алгоритму — \(O(m ^ 3 \log k + n \cdot q)\).
J. Щасливо-нещасливі паліндроми
Знайдемо для кожної щасливої цифри найдовший щасливо-нещасливий паліндром із центром у ній. Нехай довжина найдовшого паліндрома із центром у позиції \(i\) дорівнює \(d_i\). Побудуємо структуру даних для швидкого знаходження максимума на проміжку в масиві \(d\) (розріджену таблицю, дерево відрізків).
Для запиту \([l, r]\) центром найдовшого паліндрома є:
Найлівіша щаслива цифра, яка не лівіша за \(l\). Позначимо її позицію \(i\). Знайдемо довжину найдовшого паліндрома, який вміщається в проміжок \([l, r]\), використовуючи значення \(d_i\).
Найправіша щаслива цифра, яка не правіша за \(r\). Позначимо її позицію \(j\). Знайдемо довжину найдовшого паліндрома, який вміщається в проміжок \([l, r]\), використовуючи значення \(d_j\).
Щаслива цифра строго між позиціями \(i\) та \(j\). Знайдемо максимум значення \(d\) на цьому проміжку.
Ми точно знаємо, що останній запис відповідає за «підсумок дня».
Знайдемо такий проміжок \([i, n-1]\),
що сума на ньому дорівнює \(a_n\).
Зокрема він може бути порожній, якщо \(a_n=0\). Якщо такого проміжку не існує, то
відповідь — No. Інакше перейдемо до меншої задачі на масиві
\(a_{1..i-1}\).