Khu Vườn Bí Ẩn

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

Khu vườn có N cây xếp thành hàng, cây thứ i thuộc giống a_i. Có Q truy vấn, mỗi truy vấn cho l, r, hỏi tổng các giá trị a_i mà a_i xuất hiện đúng một lần (unique) trong đoạn [l, r].

Nói cách khác, tính tổng các giá trị chỉ xuất hiện chính xác 1 lần trong đoạn.

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 tổng các giá trị chỉ xuất hiện 1 lần trong đoạn [l, r].

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