Lista de probleme 2

Se dă un graf conex neorientat G cu N noduri și M muchii, fiecare muchie având asociat un cost. Un arbore parțial pentru G este un subgraf cu structura de arbore, care cuprinde toate nodurile și o parte din muchii. Se cere găsirea unui arbore parțial al grafului G, astfel încât diferența dintre cel mai mare și cel mai mic cost al unei muchii să fie minimă.

De ziua lui, Florin a primit un șir de caractere periodic și infinit. Perioada lui are lungime n și conține doar litere mici ale alfabetului englez. Deoarece este curios, el vrea să își personalizeze șirul primit în diverse moduri. Pentru a face asta, el vă dă q operații care se realizează pe șirul dat, operații de două tipuri, după cum urmează:

• 1 x y: Litera de pe poziția x devine egală cu y, unde y este o literă mică a alfabetului englez.
• 2 a b c: Florin vrea să afle câte litere egale cu c există între pozițiile [a, b] din șirul de caractere.

Fiindcă nu vrea să strice periodicitatea șirului foarte mult, Florin vă garantează că pentru toate operațiile de actualizare, valorile pozițiilor modificate au în reprezentarea binară cel mult k biți egali cu 1. Scrieţi un program care, dându-se șirul de caractere și actualizările, răspunde la interogări.