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

<syntaxhighlight lang="python" line> 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()

</syntaxhighlight>