Infinity ediția a III-a, clasa a V-a | Copilasi

Cerință

Fie $N$, un număr natural, și două șiruri de numere naturale $A$, unde $A_{i}$ reprezintă valoarea copilului $i$, și $B$, unde $B_{i}$ reprezintă culoarea copilului $i$, fiecare cu câte $N$ numere. O echipă e formată din copiii care au aceeași culoare. Se definește scorul unei echipe astfel: pentru fiecare membru al echipei se adună 1 la scor dacă cel mai apropriat membru din stânga al echipei are aceeași valoare și respectiv se adună 1 la scor dacă cel mai apropriat membru din dreapta al echipei are aceeași valoare. Se dau $Q$ query-uri de felul următor: $poz, val$, cu semnificația că valoarea elevului de pe poziția $poz$ devine $val$. Să se rezolve una din următoarele cerințe, numită $C$:

• $C=1$ se cere ca după fiecare query să se afișeze suma scorurilor tuturor echipelor;
• $C=2$ se cere ca după fiecare query să se afișeze scorul maxim și echipele care au acel scor.

Atenție! Modificările făcute la un query rămân valabile și pentru următoarele query-uri.

Date de intrare

Fișierul de intrare copilasi.in conține:

• pe prima linie trei numere naturale, $C$, $N$ și $Q$, cu semnificația din enunț;
• pe următoarea linie $N$ numere naturale, reprezentând valorile din $A$;
• pe următoarea linie $N$ numere naturale, reprezentând valorile din $B$;
• pe următoarele $Q$ linii câte o pereche de numere naturale nenule, $poz$ și $val$, cu semnificația din enunț.

Date de ieșire

Dacă $C=1$, atunci pentru fiecare query se va afișa pe câte o linie câte o valoare reprezentând suma scorurilor tuturor echipelor. Dacă $C=2$, atunci, pentru fiecare query se vor afișa pe aceeași linie separate printr-un spațiu, scorul maxim obținut de o echipă și echipele care au obținut acel scor. Răspunsurile vor fi afișate în fișierul copilasi.out.

Restricții și precizări

• $C \in \left\{1, 2\right\}$;
• $1 \leq N \leq 5 \cdot 10^{5}$;
• $1 \leq A_{i} \leq 10^{9}, 1 \leq i \leq N$;
• $1 \leq Q \leq 5 \cdot 10^{5}$;
• Pentru:
  • $C = 1$, $1 \leq B_{i} \leq 10^{6}$;
  • $C = 2$, $1 \leq B_{i} \leq 10$;

Exemplul 1

copilasi.in

1 6 4
2 3 5 2 3 6
1 2 3 1 2 3 
6 5
2 1 
5 2
2 2 

copilasi.out

6
4
4
6

Explicație

După primul query, valorile sunt: $2, 3, 5, 2, 3, 5$.
Suma valorilor echipelor este: $2+2+2=6$.

Exemplul 2

copilasi.in

2 6 4
2 3 5 2 3 6
1 2 3 1 2 3 
6 5
2 1 
5 2
2 2 

copilasi.out

2 1 2 3
2 1 3
2 1 3
2 1 2 3

Explicație

După primul query, valorile scorurilor echipelor sunt: $2,2,2$ deci scorul maxim este $2$, obținut de echipele cu indicii $1,2,3$.