3526 - String Query
De la Universitas MediaWiki
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
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.")