Rezolvare PBinfo #4400

Pentru un număr natural a definim costul ca fiind valoarea absolută (modulul) diferenței dintre a și numărul prim cel mai apropiat de a. Asupra unui șir de n numere naturale, situate pe poziții numerotate de la 1 la n, se aplică, în ordine, o succesiune de q operații. O operație constă dintr-o înlocuire și o afișare și este descrisă sub forma i x p, cu semnificația:

• mai întâi înlocuim cu x elementul din șir de pe poziția i;
• apoi afișăm suma minimă totală a costurilor unor elemente convenabil selectate de pe p poziții distincte din șir.

Cerința

Cunoscând n și cele n elemente ale șirului, scrieți un program care să determine:
1. suma costurilor tuturor elementelor din șirul dat;
2. rezultatele afișate în urma aplicării fiecăreia dintre cele q operații, date în forma precizată.

Date de intrare

Fișierul de intrare primprim.in conține pe prima linie un număr natural C, reprezentând cerința care trebuie să fie rezolvată (1 sau 2), pe a doua linie numărul natural n, cu semnificația din enunț, iar pe a treia linie cele n elemente din șir, în ordinea din șir. Dacă C = 2, pe a patra linie se află numărul natural q, reprezentând numărul de operații, iar pe următoarele q linii se află cele q operații, câte o operație pe linie, în forma descrisă în enunț. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă C = 1, fișierul de ieșire primprim.out va conține o singură linie pe care va fi afișată suma costurilor tuturor elementelor din șir. Dacă C = 2, fișierul de ieșire primprim.out va conține q linii, pe linia i fiind scris rezultatul afișat după executarea celei de a i-a operații din fișierul de intrare.

Restricții și precizări

• 1 ≤ q ≤ 2 ∗ 100.000
• 1 ≤ i, p ≤ n ≤ 1.000.000; 1 ≤ x ≤ 1.000.000
• Elementele șirului sunt numere naturale nenule mai mici sau egale cu 1.000.000.
• Datorită dimensiunilor mari ale fișierelor, nu au putut fi adăugate toate.

Exemplul 1:

primprim.in

1
5
8 1 3 5 9

primprim.out

4

Explicație

C = 1, n = 5, iar șirul este 8, 1, 3, 5, 9. Costurile elementelor sunt, în ordine, 1, 1, 0, 0, 2, deci suma este 4.

Exemplul 2:

primprim.in

2
5
8 1 3 5 9
3
2 6 4
3 5 2
5 12 5

primprim.out

2
0
3

Explicație

C = 2, n = 5, iar șirul inițial este 8, 1, 3, 5, 9. Se aplică șirului 3 operații. După prima operație, pentru care i = 2, x = 6 și p = 4, șirul devine 8, 6, 3, 5, 9. Suma minimă totală se obține dacă selectăm valorile de pe pozițiile 1, 2, 3 și 4, costurile fiind 1 + 1 + 0 + 0 = 2. După a doua operație, pentru care i = 3, x = 5 și p = 2, șirul devine 8, 6, 5, 5, 9. Selectăm valorile de pe pozițiile 3 și 4 (acestea având costul 0). După a treia operație, pentru care i = 5, x = 12 și p = 5, șirul devine 8, 6, 5, 5, 12. Selectăm toate valorile, deci suma este 1 + 1 + 0 + 0 + 1 = 3.