Problem 234: minimize

În mod misterios, Gigelivs Valerivs Maximvs Olimpicvs, un informatician din Roma antică, a fost transportat prin timp în ziua de astăzi. (Ce era un informatician în Roma antică? Un expert în utilizarea mijloacelor de calcul automate, precum abacul.)

Gigelivs este foarte surprins de tot ceea ce s-a întâmplat, însă cel mai mult îl surprind problemele de informatică din ziua de astăzi. Dacă în antichitate chiar și o alocare dinamică era considerată mare lucru, acum nu mai sunt atât de ușor de impresionat oamenii. Totuși, Gigelivs, dorind să impresioneze, vă aduce următoarea problemă.*

Se dă un șir $a_0, ... , a_{N−1}$ de N elemente și un număr K. Asupra șirului se fac $Q_M$ modificări și $Q_I$ interogări. Acestea pot fi de următoarele tipuri:

O modificare, determinată de valorile pos, val, prin care elementul $a_{pos}$ devine val.
O interogare. Definim funcția (unde cu ⊕ s-a notat operația de xor pe biți): $v(a) = (a_0 ⊕ a_1) + (a_1 ⊕ a_2) + ... + (a_{N−2} ⊕ a_{N−1})$

Se cere minimul funcției v(a) dacă schimbați valoarea a cel mult K elemente din șirul a.

Atenție! În cadrul unei operații de interogare, șirul a nu se modifică de fapt, iar aceste K schimbări de valoare nu au nicio legătură cu operația de modificare.

Protocol de interacțiune

Concurentul va implementa funcțiile:

void initialize(int N, int K, std::vector <int > a);
void modify(int pos, int val);
long long calculate();

Interacțiunea se va desfășura în felul următor:

Comisia va apela funcția initialize exact o dată, furnizând prin argumente numerele N, K și șirul a, indexat de la 0.
Comisia va apela de exact $Q_M$ ori funcția modify, furnizând prin parametri valorile pos, val menționate în enunț.
Comisia va apela de exact $Q_I$ ori funcția calculate. Concurentul trebuie să returneze răspunsul cerut, pentru valoarea curentă a șirului a.

Interactor local

Dacă doriți să vă testați local sursa, atunci este important să știți următoarele lucruri:
Grader-ul va citi de la tastatură toate informațiile din input.
Inputul trebuie sa aibă următorul format:

Linia 1: N
Linia 2: $a_0, a_1,... , a_{N−1}$
Linia 3: Q

Pe următoarele Q linii vor fi interogări sau modificări în următorul format:
0 – o interogare
1 pos val – o modificare unde elementul de pe poziția pos devine val

Interactorul va afișa răspunsurile la interogări pe o singură linie: $ans_1, ans_2, ..., ans_{Q_I}$
$Q = Q_I+Q_M$ , unde $Q$ este numărul total de interogări sau modificări, $Q_I$ este numărul de interogări, iar $Q_M$ este numărul de modificări

Restricţii

1 ≤ N ≤ 100 000
1 ≤ K ≤ 20
K ≤ N
$1 ≤ Q_I ≤ 1 \ 000$
$0 ≤ Q_M ≤ 50 \ 000$
$0 ≤ a_i < 2^{31}$
Trebuie să includeți "minimize.h"

Subtask 1 (5 puncte)

N ≤ 15
$Q_I ≤ 1 \ 000$ , $Q_M ≤ 50 \ 000$

Subtask 2 (5 puncte)

N ≤ 1 000
$Q_I = 1$ , $Q_M = 0$

Subtask 3 (10 puncte)

N ≤ 100 000
$Q_I = 1$ , $Q_M = 0$

Subtask 4 (10 puncte)

N ≤ 1 000
$Q_I ≤ 1 \ 000$ , $Q_M ≤ 50 \ 000$

Subtask 5 (30 puncte)

N ≤ 100 000
$Q_I ≤ 1 \ 000$ , $Q_M ≤ 1 \ 000$

Subtask 6 (2 puncte)

K = 1

Subtask 7 (2 puncte)

K ≤ 2

Subtask 8 (6 puncte)

K ≤ 10

Subtask 9 (30 puncte)

N ≤ 100 000
$Q_I ≤ 1 \ 000$ , $Q_M ≤ 50 \ 000$

Exemple

Considerați următorul apel:

void initialize(5, 2, [1, 9, 4, 6, 2])

Asta înseamnă că N = 5, K = 2, și a = [1, 9, 4, 6, 2]. Va urma apelul:

long long calculate()

Putem modifica șirul a în a = [4, 4, 4, 6, 2] schimbând valorile de pe pozițiile 0 și 1. Obținem v(a) = 6 care este și valoarea minimă pe care o putem obținem, deci funcția trebuie să returneze valoarea 6.

Urmează două modificări asupra șirului, definite prin următoarele apeluri.

long long modify(1, 3)

Astfel a devine [1, 3, 4, 6, 2]

long long modify(2, 3)

Astfel a devine [1, 3, 3, 6, 2]

long long calculate()

Putem modifica șirul a în a = [3, 3, 3, 3, 2] schimbând valorile de pe pozițiile 0 și 3. Obținem v(a) = 1 care este și valoarea minimă pe care o putem obținem, deci funcția trebuie să returneze valoarea 1.

minimize