Năng Lượng Xung Đột

Buổi 62 — Sqrt Decomposition & Mo
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một hệ thống gồm N hạt xếp thành dãy, hạt thứ i có loại a_i. Năng lượng xung đột của một đoạn được định nghĩa là tổng bình phương số lần xuất hiện của mỗi loại hạt trong đoạn đó. Cụ thể, nếu loại x xuất hiện f_x lần thì năng lượng = Σ(f_x^2) với mọi loại x.

Có Q truy vấn, mỗi truy vấn cho l, r, tính năng lượng xung đột của đoạn [l, r].

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 100000). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (1 ≤ a_i ≤ 100000). Q dòng tiếp theo, mỗi dòng chứa hai số nguyên l, r (1 ≤ l ≤ r ≤ N).

Dữ liệu ra

Với mỗi truy vấn, in ra năng lượng xung đột trên một dòng.

Ví dụ
Input Output
5 3\n1 2 1 2 3\n1 5\n1 3\n2 4 9\n5\n5
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 1 ≤ a_i ≤ 100000
  • 1 ≤ l ≤ r ≤ N
Draft saved