| Fişierul intrare/ieşire: | sufle.in, sufle.out | Sursă | ONI 2017, Baraj |
| Autor | Adrian Panaete, Radu Visan | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | sufle.out | Explicaţ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. |
