3526 - String Query

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

Exemplul 1:

Intrare

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

Ieșire

Datele de intrare corespund restrictiilor impuse.
2
3

Exemplul 2:

Intrare

string

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Explicație

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

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(nr_n, nr_q):

   if 1 <= nr_n <= 5000000 and 1 <= nr_q <= 250000:
       return True
   else:
       return False

def procesare_query(nr_s, nr_q, intrebare):

   for i in range(nr_q):
       nr_op, nr_x, nr_y = intrebare[i]
       if nr_op == 1:
           nr_s[nr_x - 1] = nr_y
       elif nr_op == 0:
           print(len(set(nr_s[nr_x - 1:nr_y])))

if __name__ == '__main__':

   try:
       n = int(input("Introduceti lungimea sirului: "))
       s = list(input("Introduceti sirul: "))
       q = int(input("Introduceti numarul de query-uri: "))
       query = []
       for _ in range(q):
           op, x, y = input("Introduceti query-ul: ").split()
           x = int(x)
           if op == '1':
               query.append((1, x, y))
           else:
               y = int(y)
               query.append((0, x, y))

       if verificare_restrictii(n, q):
           print("Datele de intrare corespund restrictiilor impuse.")
           procesare_query(s, q, query)
       else:
           print("Datele de intrare nu corespund restrictiilor impuse.")
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse.")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>