3526 - StringQuery

Cerinţa

Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y].

Date de intrare

Programul citește de la tastatură n, s, q si cele q query-uri.

Date de ieșire

Programul va afișa pe ecran raspunsurile la query-urile de tipul 0, fiecare pe linie nouă.

Restricţii şi precizări

• 1 ≤ n ≤ 5.000.000
• 1 ≤ q ≤ 250.000
• s este format doar din litere mici ale alfabetului englez

Exemplu

Intrare

4
aaaa
4
1 2 b
1 3 c
0 1 2
0 2 4

Ieșire

2
3

Explicatie

După primele 2 operatii, s = "abca".

Rezolvare

def distinct_characters_in_range(s, x, y):
    count = {}
    for i in range(x - 1, y):
        if s[i] not in count:
            count[s[i]] = 1
    return len(count)

def main():
    n = int(input("Introduceți lungimea șirului: "))
    s = input("Introduceți șirul: ")
    q = int(input("Introduceți numărul de query-uri: "))

    for _ in range(q):
        op, x, y = map(int, input().split())
        if op == 1:
            s = s[:x - 1] + chr(y) + s[x:]
        elif op == 0:
            result = distinct_characters_in_range(s, x, y)
            print(result)

if __name__ == "__main__":
    main()