Rezolvare PBinfo #4815

Se consideră șirul de litere mici ale alfabetului englez A[1], ..., A[N].

Fie succesiunea de caractere alăturate din șir A[x], A[x + 1], ..., A[y], unde 1 ≤ x ≤ y ≤ N, pe care o notăm cu A[x, y]. Pentru oricare literă mică a alfabetului englez l, definim range(l) ca fiind 0, dacă l apare cel mult o dată în A[x, y]. Altfel, valoarea range(l) este egală cu diferența dintre cea mai mare și cea mai mică poziție pe care litera l apare în A[x, y].
Șirul suport asociat lui A[x, y] este șirul de caractere minim lexicografic ce conține fiecare literă l de range(l) ori.

De exemplu, dacă șirul A este șirul abdacgacd și considerăm A[3, 8] = dacgac, atunci range(a) = 5 - 2 = 3 (pentru că, în A[3, 8], litera a apare pe pozițiile 2 și 5), range(c) = 6 - 3 = 3 și range(l) = 0 pentru toate celelalte litere l ∈ {b, d, e, f, g, ..., z}. Șirul suport asociat lui A[3, 8] este astfel aaaccc.

Un șir de caractere S[1] este o anagramă a șirului S[2] dacă S[1] este identic cu S[2] sau dacă S[1] se poate obține din S[2] prin schimbarea ordinii caracterelor. De exemplu, șirul de caractere tamara este o anagramă a șirului armata. Două anagrame se consideră a fi distincte dacă ele diferă în cel puțin o poziție. De exemplu, șirul de caractere aab are trei anagrame distincte: aab, aba, baa.

Asupra șirului se efectuează două tipuri de operații:

• Actualizare: dându-se litera c și poziția poz, se înlocuiește A[poz] cu c.
• Generare: dându-se perechea x, y, se generează șirul suport al lui A[x, y].

Cerințe

Problema are două cerințe, cerința de rezolvat fiind dată de C ∈ {1, 2}. Pentru ambele cerințe, se dau șirul A și M operații care se vor efectua în ordine.

• Dacă C = 1: determinați șirul suport minim lexicografic dintre cele obținute în urma tuturor operațiilor de generare.
• Dacă C = 2: pentru fiecare operație de generare dată, determinați numărul de anagrame distincte ale șirului suport obținut, modulo 1999999973.

Date de intrare

Pe prima linie a fișierului de intrare anagrame.in se află numerele naturale C, N și M, unde C este numărul cerinței (1 sau 2), iar N și M au semnificația din enunț. Pe a doua linie se află șirul A, cele N caractere ale sale nefiind separate prin spații. Pe fiecare dintre următoarele M linii se află datele care descriu câte o operație:

• O operație de actualizare este descrisă prin caracterul c și un număr natural poz, cu semnificația din enunț.
• O operație de generare este descrisă prin perechea x, y de numere naturale, cu semnificația din enunț.

Valorile aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire anagrame.out va conține:

• Dacă C = 1: pe prima linie, șirul suport minim lexicografic cerut la cerința 1.
• Dacă C = 2: pentru fiecare generare câte o linie, ce conține numărul cerut în cerința 2, în ordinea corespunzătoare generărilor date.

Restricții și precizări

• 1 ≤ N, M ≤ 100.000
• 1 ≤ x ≤ y ≤ N
• Se garantează că, pentru oricare operație de generare din testele de evaluare, șirul suport va conține cel puțin un caracter.
• În cadrul unei actualizări este permisă înlocuirea literei de pe poziția poz cu ea însăși.
• Șirul de caractere S[1], ..., S[k] este lexicografic mai mic decât șirul T[1], ..., T[l] dacă (i) k < l și S[i] = T[i] pentru oricare 1 ≤ i ≤ k, sau (ii) există un 1 ≤ i ≤ min(k, l) astfel încât S[1] = T[1], …, S[i-1] = T[i-1] și S[i] < T[i].
• Pentru 8 puncte, C = 1; N ≤ 10.000; nu există actualizări, iar șirul A are toate literele identice
• Pentru 16 puncte, C = 1; 1 ≤ N, M ≤ 500
• Pentru 24 puncte, C = 1; N ≤ 10.000; nu există actualizări
• Pentru 12 puncte, C = 1
• Pentru 8 puncte, C = 2; N ≤ 10.000; nu există actualizări, iar șirul A are toate literele identice}
• Pentru 12 puncte, C = 2; y-x ≤ 5; 1 ≤ M ≤ 50 și 1 ≤ N ≤ 10.000
• Pentru 8 puncte, C = 2; N ≤ 10.000; înainte de toate actualizările și după fiecare actualizare, șirul A nu va conține alte litere în afară de a și b
• Pentru 12 puncte, C = 2

Exemplul 1:

anagrame.in

1 5 5
abcar
b 3
1 4
r 4
r 2
2 4

anagrame.out

aaab

Explicație

După prima actualizare, șirul A devine abbar. A doua operație este o generare. Șirul suport obținut pentru abba este aaab. După următoarele două actualizări, șirul A devine arbrr, iar șirul suport pentru rbr corespunzător celei de a doua generări este rr. Șirul suport minim lexicografic dintre cele două obținute este aaab.

Exemplul 2:

anagrame.in

2 5 5
abcar
b 3
1 4
r 4
r 2
2 4

anagrame.out

4
1

Explicație

Pentru prima generare (1, 4) șirul suport obținut este aaab, care are patru anagrame distincte: aaab, aaba, abaa, baaa. După următoarele două operații, șirul suport pentru rbr este rr, care are o singură anagramă.