Nudny problem#232

Nudny problem

2,5 sekundy

256 megabajtów

Bardzo trudne

Dane jest słowo $s$ długości $n$ . Zdefiniujmy funkcję dla ciągu:

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|

Gdzie $∣ a - b ∣$ |a-b| oznacza odległość między znakami $a$ i $b$ w alfabecie. Innymi słowy, $f (s)$ oznacza sumę $∣ s_{i} - s_{j} ∣$ |s_i-s_j| dla wszystkich $1 \leq i \leq j \leq n$ 1 \le i \le j \le n. Następnie niech

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])

Gdzie $s [i .. j]$ oznacza podciąg ciągu $s$ od indeksu $i$ do $j$ . Innymi słowy, $cos t (s)$ oznacza sumę $f (s [l .. r])$ f(s[l..r]) dla wszystkich $1 \leq l \leq r \leq n$ 1 \le l \le r \le n.

Twoim zadaniem jest rozpatrzeć $q$ zapytań. Każde zapytanie zmienia element na pozycji $p$ na $c$ , tj. $s_{p} = c$ s_p = c. Wypisz $cos t (s)$ mod $1000000007$ przed rozpatrzeniem zapytań oraz po każdym rozpatrzonym zapytaniu.

Dane wejściowe

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — długość słowa $s$ .

Druga linia wejścia zawiera słowo $s$ długości $n$ .

Trzecia linia wejścia zawiera pojedynczą liczbę całkowitą $q$ ( $1 \leq q \leq 2 \cdot 1 0^{5}$ 1 \le q \le 2 \cdot 10^5) — liczbę zapytań.

Następne $q$ linii zawierają liczbę całkowitą $p$ ( $1 \leq p \leq n$ 1 \le p \le n) i znak $c$ ( $c \in {a, b, \dots, y, z}$ c \in \{a,b, \dots, y,z\}) — opis zapytań.

Dane wyjściowe

Wypisz $q + 1$ q+1 liczb całkowitych w osobnych liniach — odpowiedzi na zapytania.

Przykłady

Przykład 1

Loading

Przykład 2

Loading

Punktacja

( $3$ punkty): $n \leq 3$ n \le 3;
( $5$ punktów): $n, q \leq 50$ n,q \le 50;
( $6$ punktów): $n, q \leq 100$ n,q \le 100;
( $7$ punktów): $c, s_{i} \in {a, b}$ c,s_i \in \{a,b\};
( $20$ punktów): $n, q \leq 5000$ n,q \le 5000;
( $21$ punktów): $n, q \leq 20000$ n,q \le 20000;
( $13$ punktów): $c, s_{i} \leq$ c,s_i \le "n";
( $10$ punktów): $n, q \leq 1 0^{5}$ n,q \le 10^5;
( $15$ punktów): brak dodatkowych ograniczeń.

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}