Đế Chế Hùng Mạnh
Points
65
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Đề bài
Đế chế có N thành phố xếp thành hàng, thành phố thứ i có dân số a_i. Ban đầu có Q sắc lệnh, mỗi sắc lệnh có dạng:
- Loại 1:
1 p v— thay đổi dân số thành phố p thành v. - Loại 2:
2 l r— hỏi tổng bình phương tần suất của mỗi giá trị dân số trong đoạn [l, r]. Cụ thể, nếu giá trị x xuất hiện f_x lần thì kết quả = Σ(f_x^2).
Sử dụng Mo's algorithm with updates.
Dữ liệu vào
Dòng đầu chứa hai số nguyên N và Q (1 ≤ N ≤ 100000, 1 ≤ 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 mô tả một sắc lệnh.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra tổng bình phương tần suất trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n1 2 1 2 3\n2 1 5\n1 3 2\n2 1 5\n2 1 3 | 9\n11\n5 |
Giới hạn
- 1 ≤ N ≤ 100000
- 1 ≤ Q ≤ 100000
- 1 ≤ a_i, v ≤ 100000
- 1 ≤ p ≤ N
- 1 ≤ l ≤ r ≤ N
Community Discussion