ŠIOM — Masyvo Užklausos 2

Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Masyvo Užklausos 2

Jums duotas $n$ skaičių masyvas ir $m$ užklausų. Užklausą sudaro skaičių pora ( $i,j$ ).

Tarkime, jog $K_s$ , tai skaičiaus $s$ pasikartojimų skaičius masyvo intervale nuo $i$ iki $j$ . Pažymėkime intervalo galią kaip sumą sandaugų $K_s*K_s*s$ kiekvienam skaičiui $s$ .

Kiekvienai užklausai reikia atsakyti intervalo nuo $i$ iki $j$ ( $n_i,n_{i+1},...,n_j$ ) galią.

Pradiniai duomenys

Pirmoje eilutėje duoti du skaičiai $n,m$ - masyvo dydis bei užklausų skaičius.

Antroje eilutėje duota $n$ skaičių $a_i$ ( $1\\leqa_i\\leq10^6$ ) - masyvo elementai.

Sekančiose $m$ eilučių duota po 2 skaičius ( $i,j$ ) ( $1\\leqi\\leqj\\leqn$ ) - $i$ -toji užklausa.

Rezultatai

Kiekvienai užklausai išveskite po vieną skaičių - užklausos intervalo galią.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7	20 20 20	[2 7] -> $K_1=3,K_2=2,K_3=1$ , taigi galia lygi $3^21+2^22+1^2*3=20$

Šeštadieninė informatikos olimpiadininkų mokykla

Masyvo Užklausos 2

Pradiniai duomenys

Rezultatai

Pavyzdžiai