Boring Problem#232

Boring Problem (Editorial)

Спершу згорнемо потрійну суму в одну.

У виразі $cost (s)$ пара позицій $(i, j)$ з $i \leq j$ i \le j дає внесок $∣ s_{i} - s_{j} ∣$ |s_i - s_j| рівно стільки разів, скільки підрядків її містять, тобто $i \cdot (n - j + 1)$ i \cdot (n - j + 1). Отже,

cost (s) = i \leq j \sum i (n - j + 1) ∣ s_{i} - s_{j} ∣.

\mathrm{cost}(s) = \sum_{i \le j} i \,(n - j + 1)\, |s_i - s_j|.

Тепер зрозуміло, що для кожної позиції важливі дві ваги: «ліва» $w_{i} = i$ w_i = i і «права» $v_{i} = n - i + 1$ v_i = n - i + 1. А сама різниця $∣ s_{i} - s_{j} ∣$ |s_i - s_j| залежить лише від літер, яких усього $26$ .

Це підказує дерево відрізків, у вузлі якого зберігаємо:

$cost$ — відповідь для відрізка, що відповідає вузлу;
$W [c]$ — суму ваг $w_{i}$ w_i по позиціях відрізка з літерою $c$ ;
$V [c]$ — суму ваг $v_{i}$ v_i по позиціях відрізка з літерою $c$ .

Злиття двох вузлів: пари, у яких обидві позиції в лівій (або обидві в правій) частині, уже враховані в дитячих $cost$ . Залишаються пари « $i$ ліворуч, $j$ праворуч», для яких $i < j$ i < j, тому внесок дорівнює

c \sum d \sum ∣ c - d ∣ \cdot W_{лів} [c] \cdot V_{прав} [d] .

\sum_{c}\sum_{d} |c - d| \cdot W_{\text{лів}}[c] \cdot V_{\text{прав}}[d].

Масиви $W$ і $V$ у злитті просто додаються поелементно.

Наївно ця подвійна сума коштує $2 6^{2}$ 26^2 на злиття, що при $n, q \leq 2 \cdot 1 0^{5}$ n, q \le 2 \cdot 10^5 уже забагато. Але її легко звести до $O (26)$ : для кожного $d$

c \sum ∣ c - d ∣ W [c] = d c < d \sum W [c] - c < d \sum c W [c] + c > d \sum c W [c] - d c > d \sum W [c],

\sum_c |c-d|\, W[c] = d \!\!\sum_{c<d}\!\! W[c] - \!\!\sum_{c<d}\!\! c\,W[c] \;+\; \!\!\sum_{c>d}\!\! c\,W[c] - d \!\!\sum_{c>d}\!\! W[c],

а всі чотири суми беруться з префіксних сум масивів $W [c]$ та $c \cdot W [c]$ c \cdot W[c], які будуються за $O (26)$ .

Тоді побудова дерева коштує $O (26 n)$ , а кожен запит (зміна однієї літери) — $O (26 lo g n)$ \mathcal{O}(26 \log n), бо перераховуються лише вузли на шляху до кореня. Відповідь — $cost$ у корені; виводимо її до всіх запитів і після кожного.

Усі обчислення ведіть за модулем $1 0^{9} + 7$ 10^9+7, не забуваючи додавати модуль після віднімань.