3600 - Numbers Tree

Cerinţa

Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații:

• 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val;
• 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori);
• 3 st dr – se cere să se afișeze lungimea cele mai lungi secvențe de numere prime alcătuită exclusiv din elemente ale șirului care au indicii aflați în intervalul [st, dr](o secvență a unui șir este alcătuită din elemente aflate poziții consecutive).

Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.

Date de intrare

Fișierul de intrare numbers_tree.in conține pe prima linie numerele n și Q, reprezentând numărul de elemente ale șirului a, respectiv numărul de operații, pe a doua linie n numere naturale separate prin spații reprezentând elementele șirului inițial, iar pe următoarele Q linii sunt descrise operațiile.

Date de ieșire

Fișierul de ieșire numbers_tree.out va conține pe câte o linie răspunsurile la operațiile de tip 2 și 3 în ordinea în care acestea apar în fișierul de intrare.

Restricţii şi precizări

• 1 ≤ n, Q ≤ 100.000
• 2 ≤ a[i], val ≤ 1.000.000
• 1 ≤ st ≤ dr ≤ n

Exemplu

numbers_tree.in

7 7
2 3 4 5 6 7 8
2 1 7
3 1 7
1 2 5 4
2 2 5
3 2 5
1 2 4 3
3 1 6

numbers_tree.out

3
2
4
0
4

Rezolvare

def read_input(filename):
    with open(filename, 'r') as f:
        n, Q = map(int, f.readline().split())
        a = list(map(int, f.readline().split()))
        operations = [list(map(int, line.split())) for line in f.readlines()]
    return n, a, operations

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def apply_operation_2(a, st, dr):
    count_composite = 0
    for i in range(st - 1, dr):
        if a[i] > 1 and not is_prime(a[i]):
            count_composite += 1
    return count_composite

def apply_operation_3(a, st, dr):
    max_prime_sequence = 0
    current_prime_sequence = 0
    for i in range(st - 1, dr):
        if is_prime(a[i]):
            current_prime_sequence += 1
            max_prime_sequence = max(max_prime_sequence, current_prime_sequence)
        else:
            current_prime_sequence = 0
    return max_prime_sequence

def process_operations(n, a, operations):
    result = []
    for op in operations:
        if op[0] == 2:
            count_composite = apply_operation_2(a, op[1], op[2])
            result.append(count_composite)
        elif op[0] == 3:
            max_prime_sequence = apply_operation_3(a, op[1], op[2])
            result.append(max_prime_sequence)
    return result

def write_output(filename, result):
    with open(filename, 'w') as f:
        for res in result:
            f.write(str(res) + '\n')

def main():
    input_file = "numbers_tree.in"
    output_file = "numbers_tree.out"
    n, a, operations = read_input(input_file)
    result = process_operations(n, a, operations)
    write_output(output_file, result)

if __name__ == "__main__":
    main()