Для розвязання цієї задачі можна використати різноманісті структури даних і підходи, наприклад, дерево відрізків, дерево Фенвіка, коренева декомпозиції та інші.
У даній задачі потрібно реалізувати двійкові підйоми і пошук нанижчого спільного предка.
Визначимо, що в день \(i\) буде в кожній вершині значення рівне \(x_v + i\), будемо підтримувати такий інваріант. Тоді для обрахунку кількості квітів на шляху нам достатньо порахувати суму значень \(x_v\) і додати кількість вершин на шляху помножена на номер дня \(i\). Запит першого типу змінює \(x_v\) на \(-i\) так аби підтримувати інваріант. Тому задача перетворюється до зміни значення в вершині і обрахунку суми на шляху.
Першочергово змінимо запити, збільшити значення вершин на шляху від \(a\) до \(b\) можна розкласти на збільшення значення на шляхах до кореня від вершин \(a\), \(b\) та їх \(lca\) і окремо треба збільшити значення в \(lca\).
Розглянемо запит суми в піддереві вершини \(x\), нам треба порахувати по усіх запитах \({v, val}\) з піддерева порахувати значення \((d[v] - d[x] + 1) * val = d[x] * (-val) + (d[v] + 1) * val\), де \(d[v]\) - глибина вершини. Ми можемо порахувати в піддереві суму \(-val\) - нехай це буде \(k\), також суму значень \((d[v] + 1) * val\) - її позначемо як \(b\). Для того аби порахувати відповідь нам треба порахувати формулу \(d[x] * k + b\).
Розбір задачі доступний на сайті - Розбір районної 2022.
F. Найпростіші запити на дереві
Переформулювавши задачу на масиві можемо отримати таку задачу: додати значення усім числам на відрізку і знайти максимум на відрізку. Для цього можна використати дерево відрізків з обіцянками або лінивим оновленням.
Перетворимо рядки до маленьких букв і можна вставити ці рядки в множину (set) і вивести розмір цієї множини як відповідь.
Розбір задачі доступний на сайті - Розбір районної 2021.
Розбір задачі доступний на сайті - Розбір обласної 2017.