Lista de probleme 3

Roxana găsește noul șir \(v\) și vă adresează o întrebare: câte perechi de indici \((a, b)\), unde \(1 \le a \le b \le N\), există, cu proprietatea că suma \(xor\) a elementelor \({v}_{i}\), cu \(a \le i \le b\), este \(0\)?

Andino și-a găsit o nouă pasiune – muzica. După cum se spune, munca întotdeauna dă roade, așa că iată-l la primul lui concert! Andino, fiind un artist care a devenit popular foarte rapid, a adunat un public numeros la concertul lui, dispus sub forma unei matrice cu N linii și M coloane.

Fiecare fan al lui Andino poate avea una din cele două stări: pe vibe, codificată în structura matricei cu 1 și pe plictiseală, codificată în structura matricei cu 0. Andino a observat asta prin mulțime și dorește să schimbe starea oamenilor, așa că ia următoarea decizie: de-a lungul concertului său, Andino schimbă vibe-ul fanilor lui situați într-o submatrice definită prin colțul stânga-sus de coordonate (x1,y1) și, respectiv, prin colțul dreapta-jos de coordonate (x2,y2).

Prin schimbă vibe-ul înțelegem că starea oricărui fan se schimbă (starea devine pe vibe din pe plictiseală și vice-versa). Pe toată durata concertului, Andino schimbă vibe-ul fanilor săi de exact T ori.

La finalul concertului, Andino vrea să știe cum s-a simțit lumea la concert și îi întreabă pe Q dintre fanii săi care e starea lor. O întrebare are următoarea formă: „Care este starea fanului de coordonata xQ,yQ?”. Fiind ocupat, Andino vă roagă pe voi să-l ajutați să obțină răspunsurile la aceste întrebări.

Mugurel a decis să devină în sfârșit cel mai mare antreprenor din Imperiul Rațelor de Cauciuc. Astfel, el și-a deschis o afacere cu fructele sale preferate: portocale și banane.

Acesta primește planul recoltelor de fructe: timp de N zile, în fiecare zi Mugurel primește M grămezi de portocale și M grămezi de banane (alternativ), reprezentate prin numărul lor de kilograme.
Mugurel trebuie să împacheteze toate aceste fructe, însă producătorul său de cutii îi oferă două variante, din care poate alege doar una: fabricarea a K cutii pentru portocale și K cutii pentru banane (împachetare separată), sau fabricarea a K cutii mixte (împachetarea portocalelor și a bananelor împreună).

Însă, totul are un preț. Fie \(c_{port}\), \(c_{ban}\), \(c_{mixt}\) capacitățile cutiilor de portocale, banane respectiv mixte. Atunci, Mugurel va plăti \(A \; maci \cdot c_{port} + B \; maci \cdot c_{ban}\) sau \(C \; maci \cdot c_{mixt}\), în funcție de varianta de împachetare aleasă, unde \(A\), \(B\) și \(C\) vor fi prețuri oferite de producător. Mugurel va alege metoda de împachetare astfel încât suma de bani cheltuită să fie cât mai mică.

După ce plătește și primește cutiile, începe împachetarea. De fiecare dată când închide o cutie, o pune la finalul șirului de cutii deja închise (Mugurel se ocupă mai întâi de grămada de portocale, apoi de cea de banane). La finalul împachetării fructelor, el trebuie să împartă șirul de cutii în două șiruri consecutive, pe care le vom numi loturi.

Loturile vor fi trimise către cele două cetăți ale Imperiului, însă Mugurel nu vrea să pornească un război între cele două cetăți, așadar vrea să le împartă cu grijă. Numim discrepanță a unui lot diferența dintre cutia cu număr maxim de kilograme și cea cu număr minim. Împărțirea trebuie făcută astfel încât suma discrepanțelor celor două loturi să fie minimă, pentru împachetare.

Cu atâtea responsabilități pe cap, Mugurel vă roagă să-l ajutați cu afacerea.