Fişierul intrare/ieşire:sufle.in, sufle.outSursăONI 2017, Baraj
AutorAdrian Panaete, Radu VisanAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test2 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sufle

Sufle este un personaj cu urechi ascuţite, îndrăgostit de algoritmică. El are o antipatie profundă faţă de Aisimok, cel care îl tot provoacă să rezolve probleme folosind tot felul de formule. Sufle a botezat aceste probleme Emsiteanap.
Astăzi Aisimok i-a aruncat tânărului Sufle o nouă provocare:

Pentru oricare două numere naturale se defineşte următoarea operaţie:

  • se consideră reprezentările în baza 2 pentru cele două numere;
  • se alege o poziţie în reprezentarea binară a primului număr;
  • se schimbă cifra situată pe acea poziţie în primul număr cu cifra aflată pe exact aceeaşi poziţie în al doilea număr.

(Observaţi cum Aisimok, obsedat de matematică, nu a folosit termenul bit, tocmai pentru a-l irita pe Sufle.)

Pentru un şir oarecare de numere naturale, se poate aplica de oricâte ori şi asupra oricăror două numere operaţia descrisă mai sus. Scopul final este ca suma pătratelor numerelor din şir să ajungă la valoarea minim posibilă. Denumim costul şirului acestă valoare minimă. Pentru a deveni şi mai antipatic, Aisimok îi cere lui Sufle să calculeze aceast cost pentru mai multe subsecvenţe ale unui şir dat. Costul unei subsecvenţe este egal cu costul şirului definitit de subsecvenţa dată.

Cerinţă

Pentru un şir cunoscut şi pentru mai multe subsecvenţe date să se calculeze suma minimă a pătratelor numerelor din subsecvenţă după aplicare a operaţiei descrise, de oricâte ori se consider necesar şi asupra oricăror numere din subsecvenţă.

Date de intrare

Fişierul sufle.in conţine pe prima linie numerele natural N şi Q, reprezentând numărul de termeni din şir respective numărul de interogări. A doua linie conţine N numere naturale, termenii şirului. Pe următoarele Q linii sunt descrise interogările. Fiecare dintre aceste linii va conţine câte două numere natural L şi R capetele subsecvenţei corespunzătoare unei interogări.

Date de ieşire

Fişierul sufle.out va conţine Q linii. Pe fiecare dintre aceste linii se va afişa câte un număr, reprezentând răspunsul la interogarea corespunzătoare din fişierul de intrare.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ Q ≤ 100.000
  • 1 ≤ L ≤ R ≤ N
  • Pentru toate interogările se va considera că operaţiile se vor aplica pe şirul iniţial, fără a ţine cont de modificările rezultate din alte interogări precedente.
  • Toţi termenii din şir sunt numere naturale mai mici sau egale cu 1.000.000.

Exemplu

sufle.insufle.outExplicaţie
6 2
8 10 5 6 0 5
2 5
1 1
125
64
Se solicită răspunsul pentru două interogări:
Pentru prima interogare numerele din
subsecvenţă sunt 10, 5, 6 şi 0 care au
reprezentările binare 1010, 101, 110, 0.
Vom numerota poziţiile începând cu 1 care
corespunde ultimei cifre crescător spre cea mai
semnificativă cifră.
Aplic operaţia pentru al doilea şi al patrulea
număr pentru poziţia 1. Obţin numerele 1010,100,110,1.
Aplic operaţia pentru primul şi ultimul număr la
poziţia 2. Obţin numerele 1000, 100, 110, 11.
Numerele în baza zece sunt 8, 4, 6, 3. Suma
pătratelor 125 este minimă. Nu se poate obţine o
sumă mai mică.
La a doua interogare secvenţa conţine doar
numărul 8 deci nu se poate aplica niciodată
operaţia. Suma pătratelor se reduce la un singur
număr, pătratul lui 8 care este 64.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?