D. Хүчирхэг массив

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$a_{1}, a_{2}, ..., a_{n}$ гэсэн эерэг бүхэл тооны массив өгөгджээ. Үүний $a_{l}, a_{l + 1}..., a_{r}$ нь $1 ≤ l ≤ r ≤ n$ байх дурын дэд массив гэж үзэцгээе.

Эерэг бүхэл тоо $s$ тус бүр нь массив дахь $s$-ийн давтамжийн тоо $K_{s}$-аар илэрхийлэгднэ. Бид эерэг бүхэл тоо $s$ тус бүрийн хувьд дэд массивын зэргийг $K_{s}*K_{s}*s$ үржвэрүүдийн нийлбэр гэж нэрлэнэ. Массив дахь өөр хоорондоо адилгүй утгуудыг тоо нь төгсгөлөг тул нийлбэр нь төгсгөлөг тоо байна.

Та $t$ өгөгдсөн дэд массивуудын зэргийг тооцоолох ёстой.

Оролт

Эхний мөр нь $n$ болон $t$ ($1 ≤ n, t ≤ 200000$) гэсэн хоёр бүхэл тоо агуулах ба энэ нь массивын урт болон асуулгын тоог тус тус харуулна. Хоёр дахь мөр нь $a_{i}$ ($1 ≤ a_{i} ≤ 10^{6}$) гэсэн $n$ тооны эерэг бүхэл тоо агуулах ба энэ нь массивын элементүүдийг харуулна. Дараагийн $t$ мөрүүд нь $l$, $r$ ($1 ≤ l ≤ r ≤ n$) гэсэн хоёр эерэг бүхэл тоо агуулах ба энэ нь харгалзах дэд массивын баруун болон зүүн төгсгөлийн индексүүдийн илрэхийлнэ.

Гаралт

Гаралтын $t$ мөрүүд нь $i$ дахь мөрөнд $i$ дахь асуулгын дэд массивын зэргийг илэрхийлсэн цорын ганц эерэг бүхэл тоо агуулах ёстой. C++ дахь 64 бит бүхэл тоог унших болох бичихдээ %lld нарийвчлал ашиглахгүйг анхаарна уу. Үүний оронд cout хэсгийг ашиглах нь зүйтэй (мөн %I64d$ ашиглаж болно).

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
3 2
1 2 1
1 2
1 3
Гаралт
3
6
Оролт
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$, тиймээс зэрэг нь дараахтай тэнцүү: $3^{2}*1 + 2^{2}*2 + 1^{2}*3 = 20$.

Сэтгэгдлүүдийг ачааллаж байна...