Для розвязання цієї задачі можна використати різноманісті структури даних і підходи, наприклад, дерево відрізків, дерево Фенвіка, коренева декомпозиції та інші.
У даній задачі потрібно реалізувати двійкові підйоми і пошук нанижчого спільного предка.
Визначимо, що в день i буде в кожній вершині значення рівне xv+i, будемо підтримувати такий інваріант. Тоді для обрахунку кількості квітів на шляху нам достатньо порахувати суму значень xv і додати кількість вершин на шляху помножена на номер дня i. Запит першого типу змінює xv на −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.