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

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.")