Нудна задача#232

Нудна задача

2,5 секунди

256 мегабайтів

Дуже складна

Дано рядок $s$ довжини $n$ . Визначимо функцію від рядка:

f (s) = i = 1 \sum n j = i \sum n ∣ s_{i} - s_{j} ∣

f(s) = \displaystyle \sum_{i=1}^n \sum_{j=i}^n |s_i - s_j|

Тут $∣ a - b ∣$ |a-b| позначає відстань між символами $a$ та $b$ в алфавіті. Іншими словами, $f (s)$ позначає суму $∣ s_{i} - s_{j} ∣$ |s_i-s_j| для всіх $1 \leq i \leq j \leq n$ 1 \le i \le j \le n. Далі, визначимо

cos t (s) = i = 1 \sum n j = i \sum n f (s [i .. j])

cost(s) = \sum_{i=1}^n \sum_{j=i}^n f(s[i..j])

Тут $s [i .. j]$ позначає підрядок рядка $s$ від індексу $i$ до $j$ . Іншими словами, $cos t (s)$ позначає суму $f (s [l .. r])$ f(s[l..r]) для всіх $1 \leq l \leq r \leq n$ 1 \le l \le r \le n.

Дано $q$ запитів. Кожен запит змінює елемент на позиції $p$ на $c$ , тобто робить $s_{p} = c$ s_p = c. Вам потрібно вивести $cos t (s)$ mod $1000000007$ перед усіма запитами та після кожного запиту.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — довжину рядка $s$ .

Другий рядок містить рядок $s$ довжини $n$ .

Третій рядок містить одне ціле число $q$ ( $1 \leq q \leq 2 \cdot 1 0^{5}$ 1 \le q \le 2 \cdot 10^5) — кількість запитів.

Наступні $q$ рядків містять ціле число $p$ ( $1 \leq p \leq n$ 1 \le p \le n) та символ $c$ ( $c \in {a, b, \dots, y, z}$ c \in \{a,b, \dots, y,z\}) — опис запитів.

Вихідні дані

Виведіть $q + 1$ q+1 цілих чисел в окремих рядках — відповіді на задачу.

Приклади

Приклад 1

Loading

Приклад 2

Loading

Оцінювання

( $3$ бали): $n \leq 3$ n \le 3;
( $5$ балів): $n, q \leq 50$ n,q \le 50;
( $6$ балів): $n, q \leq 100$ n,q \le 100;
( $7$ балів): $c, s_{i} \in {a, b}$ c,s_i \in \{a,b\};
( $20$ балів): $n, q \leq 5000$ n,q \le 5000;
( $21$ бал): $n, q \leq 20000$ n,q \le 20000;
( $13$ балів): $c, s_{i} \leq$ c,s_i \le "n";
( $10$ балів): $n, q \leq 1 0^{5}$ n,q \le 10^5;
( $15$ балів): без додаткових обмежень.

f (s) = i = 1 \sum n j = i \sum n ∣ s_{i} - s_{j} ∣

∣ a - b ∣

∣ s_{i} - s_{j} ∣

1 \leq i \leq j \leq n

cos t (s) = i = 1 \sum n j = i \sum n f (s [i .. j])

f (s [l .. r])

1 \leq l \leq r \leq n

s_{p} = c

1 \leq n \leq 2 \cdot 1 0^{5}

1 \leq q \leq 2 \cdot 1 0^{5}

1 \leq p \leq n

c \in {a, b, \dots, y, z}

q + 1

n \leq 3

n, q \leq 50

n, q \leq 100

c, s_{i} \in {a, b}

n, q \leq 5000

n, q \leq 20000

c, s_{i} \leq

n, q \leq 1 0^{5}